<!DOCTYPE html>
<html lang="en">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.jpg">
  <link rel="icon" type="image/png" href="/img/favicon.jpg">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="John Doe">
  <meta name="keywords" content="">
  <title>集合源码 - Nyima&#39;s Blog</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/github-gist.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_yg9cfy8wd6.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
<meta name="generator" content="Hexo 4.2.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>Nyima</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                Home
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                Archives
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                Categories
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                Tags
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                <i class="iconfont icon-link-fill"></i>
                Links
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                About
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/img/3.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2020-10-26 10:00">
      October 26, 2020 am
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      21.4k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      291
       分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <div class="post-content mx-auto" id="post">
            
            <article class="markdown-body">
              <h1 id="集合源码"><a href="#集合源码" class="headerlink" title="集合源码"></a>集合源码</h1><p>工欲善其事必先利其器</p>
<p><a href="https://www.bilibili.com/video/BV1V7411U78L" target="_blank" rel="noopener"><strong>CodeSheep——Java源码盘起来！演示搭建JDK源码阅读环境，利用IDEA搭建Java源码阅读环境视频教程</strong></a></p>
<h2 id="ArrayList"><a href="#ArrayList" class="headerlink" title="ArrayList"></a>ArrayList</h2><h2 id="一、ArrayList底层数据结构"><a href="#一、ArrayList底层数据结构" class="headerlink" title="一、ArrayList底层数据结构"></a>一、ArrayList底层数据结构</h2><h3 id="1、ArrayList集合介绍"><a href="#1、ArrayList集合介绍" class="headerlink" title="1、ArrayList集合介绍"></a>1、ArrayList集合介绍</h3><p>ArrayList是<strong>List</strong>集合<strong>可变大小</strong>的数组的实现</p>
<h3 id="2、数组"><a href="#2、数组" class="headerlink" title="2、数组"></a>2、数组</h3><p>数组大小一旦确定，就无法改变</p>
<p><strong>增删慢</strong>：每次添加或删除元素，都需要更改数组长度、拷贝以及移动元素位置</p>
<p><strong>查询快</strong>：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素</p>
<h2 id="二、ArrayList继承关系"><a href="#二、ArrayList继承关系" class="headerlink" title="二、ArrayList继承关系"></a>二、ArrayList继承关系</h2><p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911202214.png" srcset="/img/loading.gif" alt=""></p>
<h3 id="1、Serializable标记性接口"><a href="#1、Serializable标记性接口" class="headerlink" title="1、Serializable标记性接口"></a>1、Serializable标记性接口</h3><p>此处可以查看<a href="https://www.bilibili.com/read/cv6257046" target="_blank" rel="noopener"><strong>CodeSheep——《序列化/反序列化，我忍你很久了！》</strong></a></p>
<h4 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h4><ul>
<li>类的序列化由实现<strong>java.io.Serializable</strong>接口的类启用</li>
<li>不实现此接口的类将不会使任何状态序列化或反序列化</li>
<li>可序列化类的所有子类型都是可序列化的</li>
<li>序列化接口没有方法或字段，仅<strong>用于标识可串行化的语义</strong></li>
</ul>
<p>序列化：将对象的数据写入到文件(写对象) </p>
<p>反序列化：将文件中对象的数据读取出来(读对象)</p>
<p>如果<strong>不想对某些变量进行序列化</strong>（如密码等），可以在前面加上 <strong>transient</strong> 关键字，表示该字段不想被序列化</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">Serializable</span> </span>&#123;
&#125;</code></pre>



<h4 id="案例"><a href="#案例" class="headerlink" title="案例"></a><strong>案例</strong></h4><p>Student类</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Student</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">Serializable</span> </span>&#123;
	<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">long</span> serialVersionUID = <span class="hljs-number">7515669154157983943L</span>;

	String name;
	<span class="hljs-keyword">int</span> age;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Student</span><span class="hljs-params">(String name, <span class="hljs-keyword">int</span> age)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.name = name;
		<span class="hljs-keyword">this</span>.age = age;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getName</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> name;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setName</span><span class="hljs-params">(String name)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.name = name;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getAge</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> age;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setAge</span><span class="hljs-params">(<span class="hljs-keyword">int</span> age)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.age = age;
	&#125;

	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> <span class="hljs-string">"Student&#123;"</span> +
				<span class="hljs-string">"name='"</span> + name + <span class="hljs-string">'\''</span> +
				<span class="hljs-string">", age="</span> + age +
				<span class="hljs-string">'&#125;'</span>;
	&#125;
&#125;</code></pre>



<p>测试类</p>
<pre><code class="hljs java"><span class="hljs-comment">//不使用集合</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo1</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> <span class="hljs-keyword">throws</span> IOException, ClassNotFoundException </span>&#123;
		write();
		read();
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">write</span><span class="hljs-params">()</span> <span class="hljs-keyword">throws</span> IOException </span>&#123;
		<span class="hljs-comment">//创建对象操作流，进行序列化操作</span>
		ObjectOutputStream objectOutputStream = <span class="hljs-keyword">new</span> ObjectOutputStream(<span class="hljs-keyword">new</span> FileOutputStream(<span class="hljs-string">"student.txt"</span>));
		<span class="hljs-comment">//创建Student类的对象</span>
		Student student = <span class="hljs-keyword">new</span> Student(<span class="hljs-string">"Nyima"</span>, <span class="hljs-number">12</span>);
		<span class="hljs-comment">//调用操作流写对象的方法，将对象的数据写入文件中</span>
		objectOutputStream.writeObject(student);
		<span class="hljs-comment">//关闭输出流</span>
		objectOutputStream.close();
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">read</span><span class="hljs-params">()</span> <span class="hljs-keyword">throws</span> IOException, ClassNotFoundException </span>&#123;
		ObjectInputStream objectInputStream = <span class="hljs-keyword">new</span> ObjectInputStream(<span class="hljs-keyword">new</span> FileInputStream(<span class="hljs-string">"student.txt"</span>));

		Student student = (Student) objectInputStream.readObject();
		System.out.println(student);

		objectInputStream.close();
	&#125;
&#125;

<span class="hljs-comment">//使用集合</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo2</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> <span class="hljs-keyword">throws</span> Exception</span>&#123;
		Student student1 = <span class="hljs-keyword">new</span> Student(<span class="hljs-string">"Chen"</span>, <span class="hljs-number">1</span>);
		Student student2 = <span class="hljs-keyword">new</span> Student(<span class="hljs-string">"Pan"</span>, <span class="hljs-number">1</span>);
		Student student3 = <span class="hljs-keyword">new</span> Student(<span class="hljs-string">"Wen"</span>, <span class="hljs-number">1</span>);

		ArrayList&lt;Student&gt; lists = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
		lists.add(student1);
		lists.add(student2);
		lists.add(student3);

		ObjectOutputStream oos = <span class="hljs-keyword">new</span> ObjectOutputStream(<span class="hljs-keyword">new</span> FileOutputStream(<span class="hljs-string">"stu.txt"</span>));

        <span class="hljs-comment">//通过集合进行序列化</span>
		oos.writeObject(lists);

		oos.close();

		ObjectInputStream ois = <span class="hljs-keyword">new</span> ObjectInputStream(<span class="hljs-keyword">new</span> FileInputStream(<span class="hljs-string">"stu.txt"</span>));

		lists = (ArrayList&lt;Student&gt;) ois.readObject();

		<span class="hljs-keyword">for</span>(Student student : lists) &#123;
			System.out.println(student);
		&#125;

		ois.close();
	&#125;
&#125;</code></pre>



<h3 id="2、Cloneable标记性接口"><a href="#2、Cloneable标记性接口" class="headerlink" title="2、Cloneable标记性接口"></a>2、Cloneable标记性接口</h3><p>此处可以查看<a href="https://www.bilibili.com/read/cv7349900" target="_blank" rel="noopener"><strong>CodeSheep——《一个工作三年的同事，居然还搞不清深拷贝/浅拷贝，被老大批了》</strong></a></p>
<h4 id="介绍-1"><a href="#介绍-1" class="headerlink" title="介绍"></a>介绍</h4><p>一个类<strong>实现 Cloneable 接口</strong>来指示 <strong>Object.clone()</strong> 方法，该方法对于该类的实例进行字段的复制是合法的。在不实现 Cloneable 接口的实例上调用对象的克隆方法会导致异常 CloneNotSupportedException 被抛出。</p>
<p>简言之：<strong>克隆就是依据已经有的数据，创造一份新的完全一样的数据拷贝</strong></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">interface</span> <span class="hljs-title">Cloneable</span> </span>&#123;
&#125;</code></pre>



<h4 id="条件"><a href="#条件" class="headerlink" title="条件"></a>条件</h4><ul>
<li><p>被克隆对象所在的类必须<strong>实现Cloneable接口</strong></p>
</li>
<li><p><strong>重写clone()方法</strong></p>
</li>
</ul>
<h4 id="使用"><a href="#使用" class="headerlink" title="使用"></a>使用</h4><p><strong>基本使用</strong></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo3</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		ArrayList&lt;String&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
		list.add(<span class="hljs-string">"Hello"</span>);
		list.add(<span class="hljs-string">"World"</span>);

		Object o = list.clone();

		System.out.println(o == list);
		System.out.println(list.toString());
		System.out.println(o.toString());
	&#125;
&#125;</code></pre>

<p><strong>运行结果</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200908194627.png" srcset="/img/loading.gif" alt=""></p>
<h4 id="复制过程"><a href="#复制过程" class="headerlink" title="复制过程"></a>复制过程</h4><p>在调用clone方法的地方打上断点</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200908195654.png" srcset="/img/loading.gif" alt=""></p>
<p>ArrayList实现clone()方法<strong>源码解析</strong></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> Object <span class="hljs-title">clone</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">try</span> &#123;
            <span class="hljs-comment">//此处调用了Object的clone()方法</span>
            <span class="hljs-comment">//Object的clone()方法，此处调用了本地方法(native)</span>
            <span class="hljs-comment">//protected native Object clone() throws CloneNotSupportedException;</span>
            ArrayList&lt;?&gt; v = (ArrayList&lt;?&gt;) <span class="hljs-keyword">super</span>.clone();
            
            <span class="hljs-comment">//elementData先保存了我们被复制的集合的数据，其中elementData对象为无法被序列化的Object类型的数组</span>
            <span class="hljs-comment">//size为被复制数组的大小</span>
            <span class="hljs-comment">//transient Object[] elementData; </span>
            <span class="hljs-comment">//然后调用Arrays类的copyOf方法给elementData对象赋值</span>
            <span class="hljs-comment">//copyOf()方法的调用见下面</span>
            v.elementData = Arrays.copyOf(elementData, size);
            
            <span class="hljs-comment">//用于记录此列表被记录修改的次数</span>
            v.modCount = <span class="hljs-number">0</span>;
            
            <span class="hljs-comment">//返回拷贝对象</span>
            <span class="hljs-keyword">return</span> v;
        &#125; <span class="hljs-keyword">catch</span> (CloneNotSupportedException e) &#123;
            <span class="hljs-comment">// this shouldn't happen, since we are Cloneable</span>
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> InternalError(e);
        &#125;
&#125;


<span class="hljs-comment">//copyOf()方法</span>
<span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> &lt;T,U&gt; T[] copyOf(U[] original, <span class="hljs-keyword">int</span> newLength, Class&lt;? extends T[]&gt; newType) &#123;
        <span class="hljs-meta">@SuppressWarnings</span>(<span class="hljs-string">"unchecked"</span>)
    	<span class="hljs-comment">//创建一个和原集合相同大小的集合copy</span>
        T[] copy = ((Object)newType == (Object)Object[]<span class="hljs-class">.<span class="hljs-keyword">class</span>)</span>
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    	<span class="hljs-comment">//调用System的arraycopy方法进行复制</span>
        System.arraycopy(original, <span class="hljs-number">0</span>, copy, <span class="hljs-number">0</span>,
                         Math.min(original.length, newLength));
    	<span class="hljs-comment">//返回copy集合</span>
        <span class="hljs-keyword">return</span> copy;
&#125;</code></pre>

<p><strong>图解</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200908201550.png" srcset="/img/loading.gif" alt=""></p>
<h4 id="浅拷贝"><a href="#浅拷贝" class="headerlink" title="浅拷贝"></a>浅拷贝</h4><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo4</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> <span class="hljs-keyword">throws</span> CloneNotSupportedException </span>&#123;

		Skill skill = <span class="hljs-keyword">new</span> Skill(<span class="hljs-string">"Foot Attack"</span>);
		Hero hero1 = <span class="hljs-keyword">new</span> Hero(<span class="hljs-string">"LiQing"</span>, <span class="hljs-number">25</span>, skill);

		<span class="hljs-comment">//调用hero1对象的克隆方法</span>
		Hero hero2 = hero1.clone();

		<span class="hljs-comment">//打印结果</span>
		System.out.println(hero1 == hero2);
		System.out.println(hero1);
		System.out.println(hero2);

		<span class="hljs-comment">//更改hero2的年龄和技能</span>
		hero2.setName(<span class="hljs-string">"Kasa"</span>);
		skill.setSkillName(<span class="hljs-string">"Fly in the Sky"</span>);
       	hero2.setSkill(skill);

		<span class="hljs-comment">//打印结果</span>
		System.out.println(hero1 == hero2);
		System.out.println(hero1);
		System.out.println(hero2);
	&#125;
&#125;

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Hero</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">Cloneable</span> </span>&#123;
	String name;
	<span class="hljs-keyword">int</span> age;
    <span class="hljs-comment">//技能类</span>
	Skill skill;

	<span class="hljs-comment">/**</span>
<span class="hljs-comment">	 *</span>
<span class="hljs-comment">	 * <span class="hljs-doctag">@return</span> 克隆后的对象</span>
<span class="hljs-comment">	 * <span class="hljs-doctag">@throws</span> CloneNotSupportedException</span>
<span class="hljs-comment">	 */</span>
	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">protected</span> Hero <span class="hljs-title">clone</span><span class="hljs-params">()</span> <span class="hljs-keyword">throws</span> CloneNotSupportedException </span>&#123;
		<span class="hljs-keyword">return</span> (Hero) <span class="hljs-keyword">super</span>.clone();
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Hero</span><span class="hljs-params">(String name, <span class="hljs-keyword">int</span> age, Skill skill)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.name = name;
		<span class="hljs-keyword">this</span>.age = age;
		<span class="hljs-keyword">this</span>.skill = skill;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getName</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> name;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setName</span><span class="hljs-params">(String name)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.name = name;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getAge</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> age;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setAge</span><span class="hljs-params">(<span class="hljs-keyword">int</span> age)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.age = age;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> Skill <span class="hljs-title">getSkill</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> skill;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setSkill</span><span class="hljs-params">(Skill skill)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.skill = skill;
	&#125;

	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> <span class="hljs-string">"Hero&#123;"</span> +
				<span class="hljs-string">"name='"</span> + name + <span class="hljs-string">'\''</span> +
				<span class="hljs-string">", age='"</span> + age + <span class="hljs-string">'\''</span> +
				<span class="hljs-string">", skill="</span> + skill +
				<span class="hljs-string">'&#125;'</span>;
	&#125;
&#125;

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Skill</span> </span>&#123;
	String skillName;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Skill</span><span class="hljs-params">(String skillName)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.skillName = skillName;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getSkillName</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> skillName;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setSkillName</span><span class="hljs-params">(String skillName)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.skillName = skillName;
	&#125;

	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> <span class="hljs-string">"Skill&#123;"</span> +
				<span class="hljs-string">"skillName='"</span> + skillName + <span class="hljs-string">'\''</span> +
				<span class="hljs-string">'&#125;'</span>;
	&#125;
&#125;</code></pre>

<p><strong>运行结果</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200909140608.png" srcset="/img/loading.gif" alt=""></p>
<p>说明：</p>
<p>创建了一个Hero对象hero1，然后通过其clone()方法克隆了一个hero2对象。然后<strong>我们修改hero2对象的姓名和技能</strong>，其中技能是Skill类构成的。修改后发现。hero1的name没有收到波及，但是<strong>hero1的Skill被改变了</strong></p>
<p>这就是浅拷贝存在的问题：<strong>基本数据类型可以达到完全复制，引用数据类型则不可以</strong>。这是因为在hero1被克隆的时候，其属性skill(引用数据类型)<strong>仅仅是拷贝了一份引用</strong>，因此当skill的值发生改 变时，被克隆对象hero1的属性skill也将跟随改变</p>
<h4 id="深拷贝"><a href="#深拷贝" class="headerlink" title="深拷贝"></a>深拷贝</h4><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo4</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> <span class="hljs-keyword">throws</span> CloneNotSupportedException </span>&#123;

		Skill skill = <span class="hljs-keyword">new</span> Skill(<span class="hljs-string">"Foot Attack"</span>);
		Hero hero1 = <span class="hljs-keyword">new</span> Hero(<span class="hljs-string">"LiQing"</span>, <span class="hljs-number">25</span>, skill);

		<span class="hljs-comment">//调用hero1对象的克隆方法</span>
		Hero hero2 = hero1.clone();

		<span class="hljs-comment">//打印结果</span>
		System.out.println(hero1 == hero2);
		System.out.println(hero1);
		System.out.println(hero2);

		<span class="hljs-comment">//更改hero2的年龄和技能</span>
		hero2.setName(<span class="hljs-string">"Kasa"</span>);
		skill.setSkillName(<span class="hljs-string">"Fly in the Sky"</span>);
		hero2.setSkill(skill);

		<span class="hljs-comment">//打印结果</span>
		System.out.println(hero1 == hero2);
		System.out.println(hero1);
		System.out.println(hero2);
	&#125;
&#125;


<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Hero</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">Cloneable</span> </span>&#123;
	String name;
	<span class="hljs-keyword">int</span> age;
	Skill skill;

	<span class="hljs-comment">/**</span>
<span class="hljs-comment">	 *</span>
<span class="hljs-comment">	 * <span class="hljs-doctag">@return</span> 克隆后的对象</span>
<span class="hljs-comment">	 * <span class="hljs-doctag">@throws</span> CloneNotSupportedException</span>
<span class="hljs-comment">	 */</span>
	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">protected</span> Hero <span class="hljs-title">clone</span><span class="hljs-params">()</span> <span class="hljs-keyword">throws</span> CloneNotSupportedException </span>&#123;
		<span class="hljs-comment">//克隆个英雄对象</span>
		Hero hero =  (Hero) <span class="hljs-keyword">super</span>.clone();
		
		<span class="hljs-comment">//调用Skill的clone()方法，克隆出一个skill对象，并赋值给Hero对象</span>
		<span class="hljs-keyword">this</span>.skill = <span class="hljs-keyword">this</span>.skill.clone();
	
		<span class="hljs-keyword">return</span> hero;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Hero</span><span class="hljs-params">(String name, <span class="hljs-keyword">int</span> age, Skill skill)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.name = name;
		<span class="hljs-keyword">this</span>.age = age;
		<span class="hljs-keyword">this</span>.skill = skill;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getName</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> name;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setName</span><span class="hljs-params">(String name)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.name = name;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getAge</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> age;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setAge</span><span class="hljs-params">(<span class="hljs-keyword">int</span> age)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.age = age;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> Skill <span class="hljs-title">getSkill</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> skill;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setSkill</span><span class="hljs-params">(Skill skill)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.skill = skill;
	&#125;

	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> <span class="hljs-string">"Hero&#123;"</span> +
				<span class="hljs-string">"name='"</span> + name + <span class="hljs-string">'\''</span> +
				<span class="hljs-string">", age='"</span> + age + <span class="hljs-string">'\''</span> +
				<span class="hljs-string">", skill="</span> + skill +
				<span class="hljs-string">'&#125;'</span>;
	&#125;
&#125;

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Skill</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">Cloneable</span></span>&#123;
	String skillName;

	<span class="hljs-comment">//重写克隆方法</span>
	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">protected</span> Skill <span class="hljs-title">clone</span><span class="hljs-params">()</span> <span class="hljs-keyword">throws</span> CloneNotSupportedException </span>&#123;
		<span class="hljs-keyword">return</span> (Skill)<span class="hljs-keyword">super</span>.clone();
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Skill</span><span class="hljs-params">(String skillName)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.skillName = skillName;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getSkillName</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> skillName;
	&#125;

	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setSkillName</span><span class="hljs-params">(String skillName)</span> </span>&#123;
		<span class="hljs-keyword">this</span>.skillName = skillName;
	&#125;

	<span class="hljs-meta">@Override</span>
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
		<span class="hljs-keyword">return</span> <span class="hljs-string">"Skill&#123;"</span> +
				<span class="hljs-string">"skillName='"</span> + skillName + <span class="hljs-string">'\''</span> +
				<span class="hljs-string">'&#125;'</span>;
	&#125;
&#125;</code></pre>

<p><strong>运行结果</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200909143253.png" srcset="/img/loading.gif" alt=""></p>
<p>深拷贝与浅拷贝的不同是：若被拷贝对象中引用了其他类，<strong>被引用类也需要实现Cloneable接口，并重写clone()方法</strong></p>
<p>同时被拷贝对象的clone()方法<strong>不能只是调用父类的clone()方法，需要重写</strong>，规则如下</p>
<ul>
<li><p>先调用父类的clone()方法，克隆出一个被拷贝对象</p>
<pre><code class="hljs java">Hreo hero = (Hero)<span class="hljs-keyword">super</span>.clone();</code></pre>
</li>
<li><p>调用被引用类的clone()方法，克隆出一个被引用对象</p>
<pre><code class="hljs java">Skill skill = (Skill) <span class="hljs-keyword">this</span>.skill.clone()</code></pre>
</li>
<li><p>将克隆的<strong>被引用</strong>对象赋值给<strong>被拷贝</strong>对象</p>
<pre><code class="hljs ini"><span class="hljs-attr">this.skill</span> = skill<span class="hljs-comment">;</span></code></pre>



</li>
</ul>
<h3 id="3、-RandomAccess标记性接口"><a href="#3、-RandomAccess标记性接口" class="headerlink" title="3、 RandomAccess标记性接口"></a>3、 RandomAccess标记性接口</h3><h4 id="介绍-2"><a href="#介绍-2" class="headerlink" title="介绍"></a>介绍</h4><p>标记接口由 <strong>List</strong> 实现使用，以表明它们<strong>支持快速（通常为恒定时间）随机访问</strong></p>
<p>此接口的主要目的是<strong>允许通用算法更改其行为</strong>，以便在应用于随机访问列表或顺序访问列表时提供良好的性能</p>
<h4 id="ArrayList-1"><a href="#ArrayList-1" class="headerlink" title="ArrayList"></a>ArrayList</h4><p><strong>实现了RandomAccess接口，随机访问速度比顺序访问更快</strong></p>
<p>注意ArrayList<strong>底层为数组</strong>，所以随机访问的效率高。RandomAccess接口<strong>只是用来标识其是否支持随机访问</strong>，而<strong>不是实现了该接口就能使随机访问效率更高</strong></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo1</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
        <span class="hljs-comment">//使用ArrayList</span>
		ArrayList&lt;String&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
		<span class="hljs-comment">//向list中添加十万条数据</span>
		<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; <span class="hljs-number">100000</span>; i++) &#123;
			list.add(<span class="hljs-string">"a"</span>);
		&#125;

		<span class="hljs-comment">//随机访问，并计算访问用时</span>
		<span class="hljs-keyword">long</span> startTime = System.currentTimeMillis();
		<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; <span class="hljs-number">100000</span>; i++) &#123;
			list.get(i);
		&#125;

		<span class="hljs-keyword">long</span> endTime = System.currentTimeMillis();
		System.out.println(<span class="hljs-string">"随机访问时间："</span> + (endTime - startTime));

		<span class="hljs-comment">//顺序访问</span>
		startTime = System.currentTimeMillis();
		<span class="hljs-keyword">for</span>(Iterator iterator = list.iterator(); iterator.hasNext();) &#123;
			iterator.next();
		&#125;

		endTime = System.currentTimeMillis();
		System.out.println(<span class="hljs-string">"顺序访问时间："</span> + (endTime - startTime));

	&#125;
&#125;</code></pre>

<p><strong>运行结果</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200909151646.png" srcset="/img/loading.gif" alt=""></p>
<h4 id="LinkedList"><a href="#LinkedList" class="headerlink" title="LinkedList"></a>LinkedList</h4><p><strong>LinkedLis随机访问比顺序访问更慢</strong>。因为LinkedList底层为链表，随机访问效率低，所以没有实现RandomAccess接口。</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LinkedList</span>&lt;<span class="hljs-title">E</span>&gt;</span>
<span class="hljs-class">    <span class="hljs-keyword">extends</span> <span class="hljs-title">AbstractSequentialList</span>&lt;<span class="hljs-title">E</span>&gt;</span>
<span class="hljs-class">    <span class="hljs-keyword">implements</span> <span class="hljs-title">List</span>&lt;<span class="hljs-title">E</span>&gt;, <span class="hljs-title">Deque</span>&lt;<span class="hljs-title">E</span>&gt;, <span class="hljs-title">Cloneable</span>, <span class="hljs-title">java</span>.<span class="hljs-title">io</span>.<span class="hljs-title">Serializable</span></span></code></pre>

<p><strong>代码</strong></p>
<pre><code class="hljs reasonml">public <span class="hljs-keyword">class</span> Demo2 &#123;
	public static void main(String<span class="hljs-literal">[]</span> args) &#123;
		<span class="hljs-comment">//使用LinkedList</span>
		LinkedList&lt;String&gt; <span class="hljs-built_in">list</span> = <span class="hljs-keyword">new</span> LinkedList&lt;&gt;<span class="hljs-literal">()</span>;
		<span class="hljs-comment">//向list中添加十万条数据</span>
		for (<span class="hljs-built_in">int</span> i = <span class="hljs-number">0</span>; i &lt; <span class="hljs-number">100000</span>; i++) &#123;
			<span class="hljs-built_in">list</span>.add(<span class="hljs-string">"a"</span>);
		&#125;

		<span class="hljs-comment">//随机访问，并计算访问用时</span>
		long startTime = <span class="hljs-module-access"><span class="hljs-module"><span class="hljs-identifier">System</span>.</span></span>current<span class="hljs-constructor">TimeMillis()</span>;
		for (<span class="hljs-built_in">int</span> i = <span class="hljs-number">0</span>; i &lt; <span class="hljs-number">100000</span>; i++) &#123;
			<span class="hljs-built_in">list</span>.get(i);
		&#125;

		long endTime = <span class="hljs-module-access"><span class="hljs-module"><span class="hljs-identifier">System</span>.</span></span>current<span class="hljs-constructor">TimeMillis()</span>;
		<span class="hljs-module-access"><span class="hljs-module"><span class="hljs-identifier">System</span>.</span></span>out.println(<span class="hljs-string">"随机访问时间："</span> + (endTime - startTime));

		<span class="hljs-comment">//顺序访问</span>
		startTime = <span class="hljs-module-access"><span class="hljs-module"><span class="hljs-identifier">System</span>.</span></span>current<span class="hljs-constructor">TimeMillis()</span>;
		for (Iterator iterator = <span class="hljs-built_in">list</span>.iterator<span class="hljs-literal">()</span>; iterator.has<span class="hljs-constructor">Next()</span>; ) &#123;
			iterator.next<span class="hljs-literal">()</span>;
		&#125;

		endTime = <span class="hljs-module-access"><span class="hljs-module"><span class="hljs-identifier">System</span>.</span></span>current<span class="hljs-constructor">TimeMillis()</span>;
		<span class="hljs-module-access"><span class="hljs-module"><span class="hljs-identifier">System</span>.</span></span>out.println(<span class="hljs-string">"顺序访问时间："</span> + (endTime - startTime));

	&#125;
&#125;</code></pre>

<p><strong>运行结果</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200909151730.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>为什么LinkedList随机访问的效率这么低呢</strong></p>
<ul>
<li><p>随机访问的时候源码底层<strong>每次都需要进行折半的动作</strong>，再经过判断是从头还是从尾部一个个寻找</p>
</li>
<li><p>顺序访问只会在获取迭代器的时候<strong>进行一次折半的动作</strong>，以后每次都是在上一次的基础上获取下一个元素</p>
<p>因此顺序访问要比随机访问快得多</p>
</li>
</ul>
<h4 id="应用"><a href="#应用" class="headerlink" title="应用"></a>应用</h4><p>遍历集合前使用 <strong>instanceof</strong> 关键字来判断集合<strong>是否实现了 RandomAccess 接口</strong></p>
<ul>
<li>如果实现了，就使用随机访问</li>
<li>如果没实现，就使用顺序访问</li>
</ul>
<p><strong>代码</strong></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo3</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		<span class="hljs-comment">//链表</span>
		LinkedList&lt;String&gt; linkedList = <span class="hljs-keyword">new</span> LinkedList&lt;&gt;();
		<span class="hljs-comment">//数组</span>
		ArrayList&lt;String&gt; arrayList = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();

		<span class="hljs-comment">//向集合中添加十万条数据</span>
		<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; <span class="hljs-number">100000</span>; i++) &#123;
			arrayList.add(<span class="hljs-string">"a"</span>);
			linkedList.add(<span class="hljs-string">"b"</span>);
		&#125;

		<span class="hljs-comment">//通过判断集合是否实现了RandomAccess接口，来选择适当的遍历方法</span>
		<span class="hljs-keyword">if</span> (arrayList <span class="hljs-keyword">instanceof</span> RandomAccess) &#123;
			System.out.println(<span class="hljs-string">"随机访问"</span>);
			<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; arrayList.size(); i++) &#123;
				arrayList.get(i);
			&#125;
		&#125; <span class="hljs-keyword">else</span> &#123;
			System.out.println(<span class="hljs-string">"顺序访问"</span>);
			<span class="hljs-comment">//实现了迭代器的集合，foreach会使用迭代器</span>
			<span class="hljs-keyword">for</span> (String s : arrayList) &#123;
				<span class="hljs-comment">//取出元素，不做任何操作</span>
			&#125;
		&#125;

		<span class="hljs-keyword">if</span> (linkedList <span class="hljs-keyword">instanceof</span> RandomAccess) &#123;
			System.out.println(<span class="hljs-string">"随机访问"</span>);
			<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; linkedList.size(); i++) &#123;
				linkedList.get(i);
			&#125;
		&#125; <span class="hljs-keyword">else</span> &#123;
			System.out.println(<span class="hljs-string">"顺序访问"</span>);
			<span class="hljs-comment">//实现了迭代器的集合，foreach会使用迭代器</span>
			<span class="hljs-keyword">for</span> (String s : linkedList) &#123;
				<span class="hljs-comment">//取出元素，不做任何操作</span>
			&#125;
		&#125;

	&#125;
&#125;</code></pre>



<h3 id="4、AbstractList抽象类"><a href="#4、AbstractList抽象类" class="headerlink" title="4、AbstractList抽象类"></a>4、AbstractList抽象类</h3><p>该抽象类含有一个空构造方法，以及一些需要子类去实现的抽象方法</p>
<h2 id="三、ArrayList源码分析"><a href="#三、ArrayList源码分析" class="headerlink" title="三、ArrayList源码分析"></a>三、ArrayList源码分析</h2><h3 id="1、构造方法"><a href="#1、构造方法" class="headerlink" title="1、构造方法"></a>1、构造方法</h3><h4 id="无参构造器"><a href="#无参构造器" class="headerlink" title="无参构造器"></a>无参构造器</h4><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ArrayList</span> </span>&#123;
    <span class="hljs-comment">//默认的初始化容量</span>
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_CAPACITY = <span class="hljs-number">10</span>;

    
    <span class="hljs-comment">//默认的Object类型的空数组</span>
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = &#123;&#125;;
    
    <span class="hljs-comment">//不可序列化的Object类型数组，用于存储ArrayList元素的数组</span>
    <span class="hljs-keyword">transient</span> Object[] elementData;
    
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ArrayList</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-comment">//如果没有指定集合的大小，当第一次向集合中添加元素时，集合容量会扩充为10</span>
        <span class="hljs-keyword">this</span>.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    &#125;
&#125;</code></pre>

<p>无参构造方法没有指定集合的大小，所以当<strong>第一次向集合中添加元素的时候，集合的容量会扩充为10</strong></p>
<h4 id="initialCapacity构造方法"><a href="#initialCapacity构造方法" class="headerlink" title="initialCapacity构造方法"></a>initialCapacity构造方法</h4><pre><code class="hljs java"><span class="hljs-comment">//空的Objcet类型数组，区别于DEFAULTCAPACITY_EMPTY_ELEMENTDATA</span>
<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> Object[] EMPTY_ELEMENTDATA = &#123;&#125;;

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ArrayList</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;
		<span class="hljs-comment">//如果容量大于0</span>
        <span class="hljs-keyword">if</span> (initialCapacity &gt; <span class="hljs-number">0</span>) &#123;
        	<span class="hljs-comment">//根据传入的容量大小创建Objcet类型的数组，赋值给elementData</span>
            <span class="hljs-keyword">this</span>.elementData = <span class="hljs-keyword">new</span> Object[initialCapacity];
        &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (initialCapacity == <span class="hljs-number">0</span>) &#123;
        	<span class="hljs-comment">//如果容量等于0，就将elementData赋值为一个Object类型的空数组</span>
            <span class="hljs-keyword">this</span>.elementData = EMPTY_ELEMENTDATA;
        &#125; <span class="hljs-keyword">else</span> &#123;
        	<span class="hljs-comment">//如果容量小于0，就抛出异常</span>
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">"Illegal Capacity: "</span>+
                                               initialCapacity);
        &#125;
&#125;</code></pre>

<p>initialCapacity构造函数会根据传入的容量大小来创建满足要求的集合</p>
<h4 id="Collection构造方法"><a href="#Collection构造方法" class="headerlink" title="Collection构造方法"></a>Collection构造方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ArrayList</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;
    	<span class="hljs-comment">// 将传入的集合转成数组</span>
        elementData = c.toArray();
    	
    	<span class="hljs-comment">//判断传入集合的大小是否为0</span>
        <span class="hljs-keyword">if</span> ((size = elementData.length) != <span class="hljs-number">0</span>) &#123;
            <span class="hljs-comment">// c.toArray might (incorrectly) not return Object[] (see 6260652)</span>
            <span class="hljs-comment">// 存在一个bug，c.toArray方法的返回值可能不是一个Object类型的数组</span>
            <span class="hljs-comment">// 如果elementData的类型不是一个Object类型的数组</span>
            <span class="hljs-keyword">if</span> (elementData.getClass() != Object[]<span class="hljs-class">.<span class="hljs-keyword">class</span>)</span>
<span class="hljs-class">                // 就再次进行拷贝操作</span>
<span class="hljs-class">                <span class="hljs-title">elementData</span> </span>= Arrays.copyOf(elementData, size, Object[]<span class="hljs-class">.<span class="hljs-keyword">class</span>)</span>;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-comment">// replace with empty array.</span>
            <span class="hljs-comment">// 如果传入集合的大小为0，就赋值为一个空数组</span>
            <span class="hljs-keyword">this</span>.elementData = EMPTY_ELEMENTDATA;
        &#125;
&#125;

<span class="hljs-comment">// toArray方法</span>
<span class="hljs-keyword">public</span> Object[] toArray() &#123;
    	<span class="hljs-comment">// 调用了copyOf方法</span>
        <span class="hljs-keyword">return</span> Arrays.copyOf(elementData, size);
&#125;

<span class="hljs-comment">// copyOf方法</span>
 <span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> &lt;T&gt; T[] copyOf(T[] original, <span class="hljs-keyword">int</span> newLength) &#123;
     	调用了重载后的copyOf方法，对集合进行拷贝操作
        <span class="hljs-keyword">return</span> (T[]) copyOf(original, newLength, original.getClass());
&#125;</code></pre>

<p>Collection构造方法主要是将传入的集合转变为数组类型。在转换后根据elementData的大小再次对elementData进行了赋值操作</p>
<ul>
<li>当size != 0时，要判断 c.toArray() 所返回的结果是不是Objcet类型的数组，如果不是，则还需要elementData该为Object数组</li>
<li>当size == 0时，将其赋值为一个空数组</li>
</ul>
<h3 id="2、添加方法"><a href="#2、添加方法" class="headerlink" title="2、添加方法"></a>2、添加方法</h3><h4 id="add-E-e-方法"><a href="#add-E-e-方法" class="headerlink" title="add(E e)方法"></a>add(E e)方法</h4><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo1</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		ArrayList&lt;String&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
        <span class="hljs-comment">// 向集合中添加一个元素时，会调用add(E e)方法</span>
		list.add(<span class="hljs-string">"Nyima"</span>);
	&#125;
&#125;

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">add</span><span class="hljs-params">(E e)</span> </span>&#123;
    	<span class="hljs-comment">// 传入需要扩容的最小容量，值为元素个数+1</span>
        ensureCapacityInternal(size + <span class="hljs-number">1</span>);  <span class="hljs-comment">// Increments modCount!!</span>
    	<span class="hljs-comment">// 扩容后，放入要添加的元素</span>
        elementData[size++] = e;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
&#125;


<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">ensureCapacityInternal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;
    	<span class="hljs-comment">// 调用calculateCapacity方法，计算最小容量</span>
        <span class="hljs-comment">//然后再调用ensureExplicitCapacity方法，来增加数组被修改次数modCount，以及查看是否真正需要扩容</span>
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
&#125;

<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_CAPACITY = <span class="hljs-number">10</span>;

<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">calculateCapacity</span><span class="hljs-params">(Object[] elementData, <span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;
    	<span class="hljs-comment">// 如果集合是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，也就是创建集合时没有传入容量大小，并且是第一次进行添加操作</span>
        <span class="hljs-keyword">if</span> (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) &#123;
            <span class="hljs-comment">// 返回默认容量10，和最小容量的较大者</span>
            <span class="hljs-keyword">return</span> Math.max(DEFAULT_CAPACITY, minCapacity);
        &#125;
    	<span class="hljs-comment">// 返回最小容量</span>
        <span class="hljs-keyword">return</span> minCapacity;
&#125;

 <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">ensureExplicitCapacity</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;
     	<span class="hljs-comment">// 增加modCount++</span>
        <span class="hljs-comment">// modCount用于保存集合被修改的次数</span>
        modCount++;

        <span class="hljs-comment">// overflow-conscious code</span>
     	<span class="hljs-comment">// 如果容量不够，才扩容</span>
        <span class="hljs-keyword">if</span> (minCapacity - elementData.length &gt; <span class="hljs-number">0</span>)
            <span class="hljs-comment">// 真正的扩容操作</span>
            grow(minCapacity);
&#125;

<span class="hljs-comment">// 真正的扩容操作</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">grow</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;
        <span class="hljs-comment">// overflow-conscious code</span>
    	<span class="hljs-comment">// 保存扩容前数组的容量</span>
        <span class="hljs-keyword">int</span> oldCapacity = elementData.length;
    
    	<span class="hljs-comment">// 得到扩容后数组的容量，扩大为原容量的1.5倍数</span>
    	<span class="hljs-comment">// 右移 &gt;&gt; : 右移多少位就是除以2的多少次幂，这里是除以2</span>
    	<span class="hljs-comment">// 左移 &lt;&lt; : 左移多少位就是乘以2的多少次幂</span>
        <span class="hljs-keyword">int</span> newCapacity = oldCapacity + (oldCapacity &gt;&gt; <span class="hljs-number">1</span>);
    
    	<span class="hljs-comment">// 如果扩容1.5倍后的容量小于最小容量</span>
        <span class="hljs-keyword">if</span> (newCapacity - minCapacity &lt; <span class="hljs-number">0</span>)
            <span class="hljs-comment">// 就按照最小容量进行扩容（选取较大的扩容方式）</span>
            newCapacity = minCapacity;
    
    	<span class="hljs-comment">// 如果新容量大于数组的最大容量</span>
        <span class="hljs-comment">// private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;</span>
        <span class="hljs-keyword">if</span> (newCapacity - MAX_ARRAY_SIZE &gt; <span class="hljs-number">0</span>)
            <span class="hljs-comment">//就将其令为最大容量</span>
            newCapacity = hugeCapacity(minCapacity);
    
        <span class="hljs-comment">// minCapacity is usually close to size, so this is a win:</span>
    	<span class="hljs-comment">// 将数组根据newCapacity扩容，并将其原来的元素放入到elementData中</span>
        elementData = Arrays.copyOf(elementData, newCapacity);
&#125;

<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hugeCapacity</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (minCapacity &lt; <span class="hljs-number">0</span>) <span class="hljs-comment">// overflow</span>
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> OutOfMemoryError();
        <span class="hljs-keyword">return</span> (minCapacity &gt; MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
&#125;</code></pre>

<p><strong>总结</strong></p>
<ul>
<li>向集合中添加元素时，先进行容量检测，在进行添加操作</li>
<li>容量检测操作如下<ul>
<li>最小扩容容量为<strong>当前数组元素个数+1</strong></li>
<li>判断当前数组是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，也就是调用了无参构造函数来创建集合<ul>
<li>如果是，最小容量就变为DEFAULT_CAPACITY(10)和最小容量的较大者</li>
<li>如果不是，就返回较小容量</li>
</ul>
</li>
<li>返回得到的最小扩容容量</li>
</ul>
</li>
<li>然后调用方法，<strong>增加集合被修改的次数</strong>（modCount++），然后<strong>再次确定最小扩容容量是否大于数组当前的大小</strong>（也就是放入元素后会不会大于数组的当前长度，<strong>容量不足</strong>），如果满足，则调用<strong>最重要的grow方法</strong>进行数组的扩容，方法执行的操作如下<ul>
<li>用变量<strong>oldCapacity</strong>保存扩容前数组的大小（<strong>数组中元素的个数</strong>）</li>
<li>进行扩容，<strong>扩容大小为原容量的1.5倍</strong>（右移一位，表示除以2）</li>
<li>查看扩容后的容量是否小于最小扩容容量（如果原容量为0，如初始化了集合大小，newCapaticy就还是0，所以需要比较）<ul>
<li>如果是，就以最小扩容容量来进行扩容</li>
<li>如果不是，就扩大为原容量的1.5倍</li>
</ul>
</li>
</ul>
</li>
</ul>
<p><strong>补充：</strong>集合在被操作的时候，都会增加modCount的值，那么这个值到底有什么用呢？</p>
<p>在使用迭代器进行迭代时会用到这个变量。<strong>这个变量是用来保证线程的安全性的</strong>。如果在进行迭代的时候，发现modCount的值被修改了，那么就会抛出ConcurrentModificationException</p>
<p><strong>后面分析迭代器时，还会具体分析modCount</strong></p>
<h4 id="add-int-index-E-element-方法"><a href="#add-int-index-E-element-方法" class="headerlink" title="add(int index, E element)方法"></a>add(int index, E element)方法</h4><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo1</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		ArrayList&lt;String&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;(<span class="hljs-number">1</span>);
		list.add(<span class="hljs-string">"Nyima1"</span>);
		list.add(<span class="hljs-string">"Nyima2"</span>);
		list.add(<span class="hljs-string">"Nyima3"</span>);
		<span class="hljs-comment">//向指定位置插入元素</span>
		list.add(<span class="hljs-number">1</span>, <span class="hljs-string">"Nyima4"</span>);
	&#125;
&#125;

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">add</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index, E element)</span> </span>&#123;
    	<span class="hljs-comment">// 判断插入的位置是否合法</span>
        rangeCheckForAdd(index);

    	<span class="hljs-comment">// 对数组容量进行检查，查看是否需要进行扩容，并增加数组被修改的次数modCount</span>
        ensureCapacityInternal(size + <span class="hljs-number">1</span>);  <span class="hljs-comment">// Increments modCount!!</span>
    
    	<span class="hljs-comment">/**</span>
<span class="hljs-comment">        * 进行拷贝操作，将插入位置及其后面的所有元素后移一位</span>
<span class="hljs-comment">    	* <span class="hljs-doctag">@param</span>      src      the source array.</span>
<span class="hljs-comment">        * <span class="hljs-doctag">@param</span>      srcPos   starting position in the source array.</span>
<span class="hljs-comment">     	* <span class="hljs-doctag">@param</span>      dest     the destination array.</span>
<span class="hljs-comment">     	* <span class="hljs-doctag">@param</span>      destPos  starting position in the destination data.</span>
<span class="hljs-comment">        * <span class="hljs-doctag">@param</span>      length   the number of array elements to be copied.</span>
<span class="hljs-comment">        */</span>
        System.arraycopy(elementData, index, elementData, index + <span class="hljs-number">1</span>,
                         size - index);
    
    	<span class="hljs-comment">// 在目标位置插入该元素</span>
        elementData[index] = element;
    	<span class="hljs-comment">// 集合容量加1</span>
        size++;
&#125;


<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">rangeCheckForAdd</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;
    	<span class="hljs-comment">// 如果插入位置超出了数组的范围，就抛出异常</span>
        <span class="hljs-keyword">if</span> (index &gt; size || index &lt; <span class="hljs-number">0</span>)
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IndexOutOfBoundsException(outOfBoundsMsg(index));
&#125;</code></pre>



<h4 id="addAll-Collection-lt-extends-E-gt-c-方法"><a href="#addAll-Collection-lt-extends-E-gt-c-方法" class="headerlink" title="addAll(Collection&lt;? extends E&gt; c)方法"></a>addAll(Collection&lt;? extends E&gt; c)方法</h4><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo1</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		ArrayList&lt;String&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;(<span class="hljs-number">1</span>);
		ArrayList&lt;String&gt; list2 = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();

		list.add(<span class="hljs-string">"Nyima1"</span>);
		list.add(<span class="hljs-string">"Nyima2"</span>);
		list.add(<span class="hljs-string">"Nyima3"</span>);
        
        <span class="hljs-comment">// 此处调用了addAll方法，将list集合中的所有元素插入到list2集合的末尾</span>
		list2.addAll(list);
	&#125;
&#125;

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">addAll</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;
    	<span class="hljs-comment">// 将要插入的集合转为Object类型的数组</span>
        Object[] a = c.toArray();
    
    	<span class="hljs-comment">// 得到插入数组的长度</span>
        <span class="hljs-keyword">int</span> numNew = a.length;
    
    	<span class="hljs-comment">// 增加modCount并根据需求进行扩容</span>
        ensureCapacityInternal(size + numNew);  <span class="hljs-comment">// Increments modCount</span>
    
    	<span class="hljs-comment">// 调用数组拷贝的方法，将数组a中的所有元素添加到elementData数组的末尾</span>
        System.arraycopy(a, <span class="hljs-number">0</span>, elementData, size, numNew);
    
    	<span class="hljs-comment">// 数组的大小增加，增加大小为被拷贝集合的大小</span>
        size += numNew;
    
    	<span class="hljs-comment">// 返回是否添加成功。如果被添加集合是一个空数组，则添加失败</span>
        <span class="hljs-keyword">return</span> numNew != <span class="hljs-number">0</span>;
&#125;</code></pre>



<h4 id="addAll-int-index-Collection-lt-extends-E-gt-c-方法"><a href="#addAll-int-index-Collection-lt-extends-E-gt-c-方法" class="headerlink" title="addAll(int index, Collection&lt;? extends E&gt; c)方法"></a>addAll(int index, Collection&lt;? extends E&gt; c)方法</h4><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo1</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		ArrayList&lt;String&gt; list = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;(<span class="hljs-number">1</span>);
		ArrayList&lt;String&gt; list2 = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
		ArrayList&lt;String&gt; list3 = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();

		list.add(<span class="hljs-string">"Nyima1"</span>);
		list.add(<span class="hljs-string">"Nyima2"</span>);
		list.add(<span class="hljs-string">"Nyima3"</span>);

		list2.add(<span class="hljs-string">"Nyima4"</span>);
		list2.add(<span class="hljs-string">"Nyima5"</span>);
	
        <span class="hljs-comment">// 在指定位置插入所有集合</span>
		list2.addAll(<span class="hljs-number">1</span>, list);
	&#125;
&#125;

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">addAll</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index, Collection&lt;? extends E&gt; c)</span> </span>&#123;
    	<span class="hljs-comment">// 进行边界检查，如果超出集合范围，则会抛出异常</span>
        rangeCheckForAdd(index);
		
    	<span class="hljs-comment">// 将要插入的集合转为Object类型的数组</span>
        Object[] a = c.toArray();
    	
    	<span class="hljs-comment">// 得到插入数组的长度</span>
        <span class="hljs-keyword">int</span> numNew = a.length;
       
    	<span class="hljs-comment">// 根据需求进行扩容操作</span>
        ensureCapacityInternal(size + numNew);  <span class="hljs-comment">// Increments modCount</span>
		
    	<span class="hljs-comment">// 计算需要移动的步数</span>
        <span class="hljs-keyword">int</span> numMoved = size - index;
    
    	<span class="hljs-comment">// 如果需要移动的步数大于0， 则进行移动操作</span>
        <span class="hljs-keyword">if</span> (numMoved &gt; <span class="hljs-number">0</span>)
            <span class="hljs-comment">// 先将被插入数组中在index之后的元素向后移动</span>
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
		
    	<span class="hljs-comment">// 在指定位置插入数组</span>
        System.arraycopy(a, <span class="hljs-number">0</span>, elementData, index, numNew);
    
    	<span class="hljs-comment">// 增加size的大小</span>
        size += numNew;
    
    	<span class="hljs-comment">// 返回是否插入成功</span>
        <span class="hljs-keyword">return</span> numNew != <span class="hljs-number">0</span>;
&#125;</code></pre>

<p>这里的插入操作和 add(int index, E element) 方法有一些类似。边界判断、集合转数组、数组扩容等。并且<strong>在移动被插入数组中的元素时，都用到了 System.arraycopy() 方法</strong>。只不过 add(int index, E element) 只用插入一个元素，所以直接插入就可以了。而 a<strong>ddAll(int index, Collection&lt;? extends E&gt; c) 方法</strong>因为需要插入多个元素，所以<strong>再次用到了 System.arraycopy()  方法</strong>，来进行多个元素的插入操作</p>
<h3 id="3、移除方法"><a href="#3、移除方法" class="headerlink" title="3、移除方法"></a>3、移除方法</h3><h4 id="remove-int-index-方法"><a href="#remove-int-index-方法" class="headerlink" title="remove(int index)方法"></a>remove(int index)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">remove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;
        <span class="hljs-comment">// 判断是否越界</span>
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);
		
    	<span class="hljs-comment">// 需要移动的元素个数</span>
        <span class="hljs-keyword">int</span> numMoved = size - index - <span class="hljs-number">1</span>;
    	
    	<span class="hljs-comment">// 从index+1开始，后面的元素全部前移1位</span>
        <span class="hljs-keyword">if</span> (numMoved &gt; <span class="hljs-number">0</span>)
            System.arraycopy(elementData, index+<span class="hljs-number">1</span>, elementData, index,
                             numMoved);
    
    	<span class="hljs-comment">// 让最后一个元素置空，让GC来清楚它</span>
        elementData[--size] = <span class="hljs-keyword">null</span>; <span class="hljs-comment">// clear to let GC do its work</span>
		
    	<span class="hljs-comment">// 返回被移除的元素</span>
        <span class="hljs-keyword">return</span> oldValue;
&#125;</code></pre>



<h4 id="remove-Object-o-方法"><a href="#remove-Object-o-方法" class="headerlink" title="remove(Object o)方法"></a>remove(Object o)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">remove</span><span class="hljs-params">(Object o)</span> </span>&#123;
    <span class="hljs-comment">// 被移除的元素为空</span>
    <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">null</span>) &#123;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>; index &lt; size; index++)
            <span class="hljs-comment">// 移除为空的元素</span>
            <span class="hljs-keyword">if</span> (elementData[index] == <span class="hljs-keyword">null</span>) &#123;
                fastRemove(index);
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
            &#125;
    &#125; <span class="hljs-keyword">else</span> &#123;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>; index &lt; size; index++)
            <span class="hljs-comment">// 移除指定的元素</span>
            <span class="hljs-keyword">if</span> (o.equals(elementData[index])) &#123;
                <span class="hljs-comment">// 每次删除一个元素</span>
                fastRemove(index);
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
            &#125;
    &#125;
    <span class="hljs-comment">// 移除失败</span>
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
&#125;

<span class="hljs-comment">// 这个方法和remove(int index)方法有些类似，只不过不用返回被删除的元素</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">fastRemove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;
        modCount++;
        <span class="hljs-keyword">int</span> numMoved = size - index - <span class="hljs-number">1</span>;
        <span class="hljs-keyword">if</span> (numMoved &gt; <span class="hljs-number">0</span>)
            System.arraycopy(elementData, index+<span class="hljs-number">1</span>, elementData, index,
                             numMoved);
    
    	<span class="hljs-comment">// 让最后一个元素置空，让GC来清楚它</span>
        elementData[--size] = <span class="hljs-keyword">null</span>; <span class="hljs-comment">// clear to let GC do its work</span>
&#125;</code></pre>





<h3 id="4、set-get方法"><a href="#4、set-get方法" class="headerlink" title="4、set/get方法"></a>4、set/get方法</h3><h4 id="set-int-index-E-element-方法"><a href="#set-int-index-E-element-方法" class="headerlink" title="set(int index, E element)方法"></a>set(int index, E element)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">set</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index, E element)</span> </span>&#123;
    	<span class="hljs-comment">// 判断索引是否越界</span>
        rangeCheck(index);
		
    	<span class="hljs-comment">// 用oldValue保存数组中index位置上的元素</span>
        E oldValue = elementData(index);
    
    	<span class="hljs-comment">// 将要插入的元素插入到数组的index位置上</span>
        elementData[index] = element;
    
    	<span class="hljs-comment">// 返回index原来位置上的元素</span>
        <span class="hljs-keyword">return</span> oldValue;
&#125;</code></pre>

<p>set方法在改变数组中指定位置的元素时，<strong>会返回被覆盖的元素</strong></p>
<h4 id="get-int-index-方法"><a href="#get-int-index-方法" class="headerlink" title="get(int index)方法"></a>get(int index)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">get</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;
    	<span class="hljs-comment">// 判断索引是否越界</span>
        rangeCheck(index);
 
    	<span class="hljs-comment">// 返回数组中index位置上的元素</span>
        <span class="hljs-keyword">return</span> elementData(index);
&#125;</code></pre>



<h3 id="5、转化方法"><a href="#5、转化方法" class="headerlink" title="5、转化方法"></a>5、转化方法</h3><h4 id="toString-方法"><a href="#toString-方法" class="headerlink" title="toString()方法"></a>toString()方法</h4><p>ArrayList 的 toString 方法调用的是其祖宗类 AbstractCollection 的toString 方法</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910150556.png" srcset="/img/loading.gif" alt=""></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-keyword">abstract</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">AbstractCollection</span>&lt;<span class="hljs-title">E</span>&gt; <span class="hljs-keyword">implements</span> <span class="hljs-title">Collection</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-comment">// 获取迭代器</span>
        Iterator&lt;E&gt; it = iterator();
        <span class="hljs-comment">// 如果迭代器为空，就返回"[]"</span>
        <span class="hljs-keyword">if</span> (! it.hasNext())
            <span class="hljs-keyword">return</span> <span class="hljs-string">"[]"</span>;
	
        <span class="hljs-comment">// 使用StringBuilder来进行字符串的拼接</span>
        StringBuilder sb = <span class="hljs-keyword">new</span> StringBuilder();
        sb.append(<span class="hljs-string">'['</span>);
        <span class="hljs-keyword">for</span> (;;) &#123;
            <span class="hljs-comment">// 获取一个元素</span>
            E e = it.next();
            
            <span class="hljs-comment">// 进行拼接操作</span>
            sb.append(e == <span class="hljs-keyword">this</span> ? <span class="hljs-string">"(this Collection)"</span> : e);
            
            <span class="hljs-comment">// 看是否还有下一个元素</span>
            <span class="hljs-keyword">if</span> (! it.hasNext())
                <span class="hljs-comment">// 如果没有，就加上']'，并调用toStrng方法转化为String类型</span>
                <span class="hljs-keyword">return</span> sb.append(<span class="hljs-string">']'</span>).toString();
            
            <span class="hljs-comment">// 如果还有下一个元素，就加上 ", " 进行分割</span>
            sb.append(<span class="hljs-string">','</span>).append(<span class="hljs-string">' '</span>);
        &#125;
    &#125;
&#125;</code></pre>



<h3 id="6、迭代器"><a href="#6、迭代器" class="headerlink" title="6、迭代器"></a>6、迭代器</h3><h4 id="iterator-普通迭代器"><a href="#iterator-普通迭代器" class="headerlink" title="iterator()普通迭代器"></a>iterator()普通迭代器</h4><p><strong>案例一</strong>：使用迭代器<strong>遍历</strong>获取集合的每一个元素</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> Iterator&lt;E&gt; <span class="hljs-title">iterator</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Itr();
&#125;

<span class="hljs-comment">// Itr为ArrayList中的内部类</span>
<span class="hljs-keyword">private</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Itr</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">Iterator</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;
    	<span class="hljs-comment">// 光标，用于指向下次被查看的元素。 一开始为0</span>
        <span class="hljs-keyword">int</span> cursor;       <span class="hljs-comment">// index of next element to return</span>
    	<span class="hljs-comment">// 最后一个元素的索引，如果没有元素就是-1</span>
        <span class="hljs-keyword">int</span> lastRet = -<span class="hljs-number">1</span>; <span class="hljs-comment">// index of last element returned; -1 if no such</span>
    
    	<span class="hljs-comment">// 期望的被修改次数 = 开始迭代时被修改的次数。主要是为了检查多线程情况下，是否出现了并发安全性问题</span>
        <span class="hljs-keyword">int</span> expectedModCount = modCount;
	
    	<span class="hljs-comment">// 无参构造函数</span>
        Itr() &#123;&#125;
	
    	<span class="hljs-comment">// 查看是否到了末尾， 如果光标和数组大小相等，则到了末尾</span>
        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">hasNext</span><span class="hljs-params">()</span> </span>&#123;
            <span class="hljs-keyword">return</span> cursor != size;
		&#125;

        <span class="hljs-meta">@SuppressWarnings</span>(<span class="hljs-string">"unchecked"</span>)
        <span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">next</span><span class="hljs-params">()</span> </span>&#123;
            <span class="hljs-comment">// 检查是否有并发安全性问题</span>
            checkForComodification();
            
            <span class="hljs-comment">// i 用来访问数组中的元素。 把光标的值赋值给i</span>
            <span class="hljs-keyword">int</span> i = cursor;
            
            <span class="hljs-comment">// 如果越界，抛出异常</span>
            <span class="hljs-keyword">if</span> (i &gt;= size)
                <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NoSuchElementException();
            
            <span class="hljs-comment">// 将被迭代的数组赋值给elementData</span>
            Object[] elementData = ArrayList.<span class="hljs-keyword">this</span>.elementData;
            
            <span class="hljs-comment">// 是否越界</span>
            <span class="hljs-keyword">if</span> (i &gt;= elementData.length)
                <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> ConcurrentModificationException();
            
            <span class="hljs-comment">// 光标后移</span>
            cursor = i + <span class="hljs-number">1</span>;
            
            <span class="hljs-comment">// 给lastRet赋值，同时返回 i 指向的元素</span>
            <span class="hljs-keyword">return</span> (E) elementData[lastRet = i];
        &#125;

       
        <span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">checkForComodification</span><span class="hljs-params">()</span> </span>&#123;
            <span class="hljs-comment">// 看当前的 modCount 和迭代开始前的 modCount (expectedModCount)是否相同</span>
            <span class="hljs-keyword">if</span> (modCount != expectedModCount)
                <span class="hljs-comment">// 如果不同，抛出异常</span>
                <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> ConcurrentModificationException();
        &#125;
&#125;</code></pre>



<p><strong>案例二</strong>：在使用迭代器遍历元素时，删除<strong>最后一个</strong>元素</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo3</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		ArrayList&lt;String&gt; arrayList = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
		arrayList.add(<span class="hljs-string">"Nyima1"</span>);
		arrayList.add(<span class="hljs-string">"Nyima2"</span>);
		arrayList.add(<span class="hljs-string">"Nyima3"</span>);

		Iterator iterator = arrayList.iterator();

		<span class="hljs-keyword">while</span> (iterator.hasNext()) &#123;
			String tempStr = (String) iterator.next();
            <span class="hljs-comment">// 移除最后一个元素</span>
			<span class="hljs-keyword">if</span>(tempStr.equals(<span class="hljs-string">"Nyima3"</span>)) &#123;
				arrayList.remove(tempStr);
			&#125;
		&#125;
	&#125;
&#125;</code></pre>

<p><strong>运行结果</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910163121.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>问题分析</strong></p>
<ul>
<li><p>每次进行遍历操作调用 next 方法时，在开头都会先调用<strong>checkForComodification</strong>方法，<strong>来判断modCount是否和expectedModCount是否一致</strong></p>
<ul>
<li><p>在删除指定元素前的遍历中，可以看到 modCount 和 expectedModCount 相同，都为3</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910163407.png" srcset="/img/loading.gif" alt=""></p>
</li>
</ul>
</li>
<li><p>进行删除操作，<strong>删除操作会使得数组的大小-1</strong><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910163528.png" srcset="/img/loading.gif" alt=""></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">remove</span><span class="hljs-params">(Object o)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>; index &lt; size; index++)
                <span class="hljs-keyword">if</span> (elementData[index] == <span class="hljs-keyword">null</span>) &#123;
                    fastRemove(index);
                    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
                &#125;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>; index &lt; size; index++)
                <span class="hljs-keyword">if</span> (o.equals(elementData[index])) &#123;
                    fastRemove(index);
                    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
                &#125;
        &#125;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    &#125;

    <span class="hljs-comment">/*</span>
<span class="hljs-comment">     * Private remove method that skips bounds checking and does not</span>
<span class="hljs-comment">     * return the value removed.</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">fastRemove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;
        modCount++;
        <span class="hljs-keyword">int</span> numMoved = size - index - <span class="hljs-number">1</span>;
        <span class="hljs-keyword">if</span> (numMoved &gt; <span class="hljs-number">0</span>)
            System.arraycopy(elementData, index+<span class="hljs-number">1</span>, elementData, index,
                             numMoved);
        
        <span class="hljs-comment">// 这里会使得数组的大小-1</span>
        elementData[--size] = <span class="hljs-keyword">null</span>; <span class="hljs-comment">// clear to let GC do its work</span>
    &#125;</code></pre>
</li>
<li><p>继续向下执行，会发现在遍历了所有元素之后，<strong>循环并没有第一时间就停下来</strong>！</p>
<ul>
<li>可以看到，hasNext 是<strong>根据光标和数组大小是否一致来判断是否有下一个元素的</strong></li>
</ul>
</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910163802.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>再次执行next，此时发现<strong>modCount是否和expectedModCount不一致！</strong>便抛出了异常<ul>
<li>modCount的增加是因为<strong>前面进行了删除操作，使得modCount的值+1了</strong></li>
</ul>
</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910164004.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>结论</strong>：在使用迭代器进行遍历时，如果中途<strong>移除了最后一个元素</strong>，则会出现<strong>并发修改异常</strong>。因为在遍历过程中modCount的值被修改了</p>
<p><strong>案例三</strong>：使用迭代器删除<strong>倒数第二个</strong>元素</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo3</span> </span>&#123;
	<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
		ArrayList&lt;String&gt; arrayList = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
		arrayList.add(<span class="hljs-string">"Nyima1"</span>);
		arrayList.add(<span class="hljs-string">"Nyima2"</span>);
		arrayList.add(<span class="hljs-string">"Nyima3"</span>);

		Iterator iterator = arrayList.iterator();

		<span class="hljs-keyword">while</span> (iterator.hasNext()) &#123;
			String tempStr = (String) iterator.next();
            <span class="hljs-comment">// 移除倒数第二个元素</span>
			<span class="hljs-keyword">if</span>(tempStr.equals(<span class="hljs-string">"Nyima2"</span>)) &#123;
				arrayList.remove(tempStr);
			&#125;
		&#125;
	&#125;
&#125;</code></pre>

<p><strong>运行结果</strong>：没有抛出异常</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910165928.png" srcset="/img/loading.gif" alt=""></p>
<p>问题分析：</p>
<ul>
<li><p>在删除第二个元素的时候，modCount确实增加了 3-&gt;4</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910170113.png" srcset="/img/loading.gif" alt=""></p>
</li>
<li><p>因为删除了一个元素，<strong>此时的数组大小 size = 2，与光标cursor的大小一致了</strong> ！</p>
</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200910170139.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>所以<strong>还没来得及做下一次 modCount 和 expectedModCount 的检测，就跳出了循环</strong></li>
</ul>
<p>在遍历ArrayList时，不要对集合中的元素进行增加与修改操作。如果要进行元素的<strong>删除</strong>，最好<strong>使用迭代器自身的 remove() 方法</strong></p>
<pre><code class="hljs java">iterator.remove();</code></pre>



<h4 id="迭代器默认remove-方法"><a href="#迭代器默认remove-方法" class="headerlink" title="迭代器默认remove()方法"></a>迭代器默认remove()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">remove</span><span class="hljs-params">()</span> </span>&#123;
    <span class="hljs-keyword">if</span> (lastRet &lt; <span class="hljs-number">0</span>)
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalStateException();
    
    <span class="hljs-comment">// 调用方法检测 modCount 和 expectedModCount，此时还未进行删除操作，所以两个值相同</span>
    checkForComodification();

    <span class="hljs-keyword">try</span> &#123;
        <span class="hljs-comment">// 调用ArrayList的remove(index)方法进行删除，此操作会修改modCount的值</span>
        ArrayList.<span class="hljs-keyword">this</span>.remove(lastRet);  
        cursor = lastRet;
        lastRet = -<span class="hljs-number">1</span>;
        
        <span class="hljs-comment">// 更新 expectedModCount 的值</span>
        expectedModCount = modCount;
    &#125; <span class="hljs-keyword">catch</span> (IndexOutOfBoundsException ex) &#123;
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> ConcurrentModificationException();
    &#125;
&#125;</code></pre>

<p>可以看出，<strong>迭代器默认的remove方法，在进行完删除操作后，更新了 expectedModCount 的值，使得其与modCount一致</strong></p>
<h3 id="7、清空方法"><a href="#7、清空方法" class="headerlink" title="7、清空方法"></a>7、清空方法</h3><h4 id="clear-方法"><a href="#clear-方法" class="headerlink" title="clear()方法"></a>clear()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">clear</span><span class="hljs-params">()</span> </span>&#123;
    modCount++;

    <span class="hljs-comment">// clear to let GC do its work</span>
    <span class="hljs-comment">// 依次将数组中的元素置为null，方便GC来回收内存</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; size; i++)
        elementData[i] = <span class="hljs-keyword">null</span>;

    <span class="hljs-comment">// 将容量设置为0</span>
    size = <span class="hljs-number">0</span>;
&#125;</code></pre>



<h3 id="8、包含方法"><a href="#8、包含方法" class="headerlink" title="8、包含方法"></a>8、包含方法</h3><h4 id="contains-Object-o-方法"><a href="#contains-Object-o-方法" class="headerlink" title="contains(Object o)方法"></a>contains(Object o)方法</h4><pre><code class="hljs java"><span class="hljs-comment">// 将参数转为了Object类型</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">contains</span><span class="hljs-params">(Object o)</span> </span>&#123;
    <span class="hljs-comment">// 调用 indexOf 方法，查找o的索引。如果索引值大于等于0，就返回true，反之返回false</span>
    <span class="hljs-keyword">return</span> indexOf(o) &gt;= <span class="hljs-number">0</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">indexOf</span><span class="hljs-params">(Object o)</span> </span>&#123;
    	<span class="hljs-comment">// 传入参数是否为 null</span>
        <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-comment">// 依次遍历数组，返回遇到的第一个null的索引</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; size; i++)
                <span class="hljs-keyword">if</span> (elementData[i]==<span class="hljs-keyword">null</span>)
                    <span class="hljs-keyword">return</span> i;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-comment">// 遍历数组，返回遇到的第一个o的索引</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; size; i++)
                <span class="hljs-keyword">if</span> (o.equals(elementData[i]))
                    <span class="hljs-keyword">return</span> i;
        &#125;
    	<span class="hljs-comment">// 如果数组中没有该元素，就返回-1</span>
        <span class="hljs-keyword">return</span> -<span class="hljs-number">1</span>;
&#125;</code></pre>



<h1 id="LinkedList-1"><a href="#LinkedList-1" class="headerlink" title="LinkedList"></a>LinkedList</h1><h2 id="一、LinkedList底层数据结构"><a href="#一、LinkedList底层数据结构" class="headerlink" title="一、LinkedList底层数据结构"></a>一、LinkedList底层数据结构</h2><h3 id="1、LinkedList集合介绍"><a href="#1、LinkedList集合介绍" class="headerlink" title="1、LinkedList集合介绍"></a>1、LinkedList集合介绍</h3><p>LinkedList底层由一个<strong>拥有头、尾指针的双向链表构成</strong></p>
<h3 id="2、链表"><a href="#2、链表" class="headerlink" title="2、链表"></a>2、链表</h3><p>链表的<strong>增删插入效率高</strong>，但是<strong>查找效率较低</strong></p>
<p>详细可见<a href="https://nyimac.gitee.io/2020/06/17/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/#%E4%BA%8C%E3%80%81%E9%93%BE%E8%A1%A8">Java数据结构与算法——链表</a></p>
<h2 id="二、LinkedList继承关系"><a href="#二、LinkedList继承关系" class="headerlink" title="二、LinkedList继承关系"></a>二、LinkedList继承关系</h2><h3 id="1、继承关系图"><a href="#1、继承关系图" class="headerlink" title="1、继承关系图"></a>1、继承关系图</h3><p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20201227205501.png" srcset="/img/loading.gif" alt=""></p>
<p>LinkedList也实现了Serializable和Clonealbe接口，但因为链表随机访问效率较低，所以未实现RandomAccess方法</p>
<h3 id="2、clone方法"><a href="#2、clone方法" class="headerlink" title="2、clone方法"></a>2、clone方法</h3><pre><code class="hljs php"><span class="hljs-keyword">public</span> Object <span class="hljs-keyword">clone</span>() &#123;
	<span class="hljs-comment">// 调用本地方法，将链表进行克隆，此时clone里元素与被克隆链表的元素一致</span>
    LinkedList&lt;E&gt; <span class="hljs-keyword">clone</span> = superClone();

    <span class="hljs-comment">// Put clone into "virgin" state</span>
    <span class="hljs-comment">// 克隆出来的链表的头、尾指针都为null。此时clone被清空了，因为没有指针指向clone链表的任意元素</span>
    <span class="hljs-keyword">clone</span>.first = <span class="hljs-keyword">clone</span>.last = <span class="hljs-keyword">null</span>;
    
    <span class="hljs-comment">// 克隆出来的链表size为0</span>
    <span class="hljs-keyword">clone</span>.size = <span class="hljs-number">0</span>;
    
    <span class="hljs-comment">// 修改次数为0</span>
    <span class="hljs-keyword">clone</span>.modCount = <span class="hljs-number">0</span>;

    <span class="hljs-comment">// Initialize clone with our elements</span>
    <span class="hljs-comment">// 初始化克隆链表，为其添加元素</span>
    <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; x = x.next)
        <span class="hljs-keyword">clone</span>.add(x.item);
	
	<span class="hljs-comment">// 返回克隆链表</span>
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">clone</span>;
&#125;

 <span class="hljs-keyword">private</span> LinkedList&lt;E&gt; superClone() &#123;
        <span class="hljs-keyword">try</span> &#123;
        	<span class="hljs-comment">// 调用本地方法进行克隆操作</span>
            <span class="hljs-keyword">return</span> (LinkedList&lt;E&gt;) super.<span class="hljs-keyword">clone</span>();
        &#125; <span class="hljs-keyword">catch</span> (CloneNotSupportedException e) &#123;
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> InternalError(e);
        &#125;
&#125;</code></pre>



<h2 id="三、LinkedList源码分析"><a href="#三、LinkedList源码分析" class="headerlink" title="三、LinkedList源码分析"></a>三、LinkedList源码分析</h2><h3 id="1、构造方法-1"><a href="#1、构造方法-1" class="headerlink" title="1、构造方法"></a>1、构造方法</h3><h4 id="无参构造方法"><a href="#无参构造方法" class="headerlink" title="无参构造方法"></a>无参构造方法</h4><pre><code class="hljs java"><span class="hljs-comment">// 链表的容量</span>
<span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> size = <span class="hljs-number">0</span>;

<span class="hljs-comment">// 链表的头指针</span>
<span class="hljs-keyword">transient</span> Node&lt;E&gt; first;

<span class="hljs-comment">// 链表的尾指针</span>
<span class="hljs-keyword">transient</span> Node&lt;E&gt; last;

<span class="hljs-comment">// 创建了一个空链表</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LinkedList</span><span class="hljs-params">()</span> </span>&#123;
&#125;</code></pre>



<h4 id="Collection构造方法-1"><a href="#Collection构造方法-1" class="headerlink" title="Collection构造方法"></a>Collection构造方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LinkedList</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;
    <span class="hljs-comment">// 先调用无参构造函数， 初始化集合容积 size = 0， 并创建头尾指针</span>
    <span class="hljs-keyword">this</span>();
    
    <span class="hljs-comment">// 调用方法，将传入的集合c添加到集合尾部</span>
    addAll(c);
&#125;


<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">addAll</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;
    	<span class="hljs-comment">// 调用重载后的addAll()方法，并返回其结果</span>
    	<span class="hljs-keyword">return</span> addAll(size, c);
&#125;


<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">addAll</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index, Collection&lt;? extends E&gt; c)</span> </span>&#123;
    	<span class="hljs-comment">// 检查索引是否越界， 通过0和size来判断</span>
        checkPositionIndex(index);
		
    	<span class="hljs-comment">// 将传入的集合转成Object类型的数组</span>
        Object[] a = c.toArray();
    
    	<span class="hljs-comment">// 获得传入集合的长度，也就是需要插入的集合中元素的个数</span>
        <span class="hljs-keyword">int</span> numNew = a.length;
    
    	<span class="hljs-comment">// 如果其长度为0，则返回添加失败</span>
        <span class="hljs-keyword">if</span> (numNew == <span class="hljs-number">0</span>)
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;

    	<span class="hljs-comment">// 创建两个节点</span>
    	<span class="hljs-comment">// pred保存插入位置的前驱节点， succ保存插入位置的节点</span>
        Node&lt;E&gt; pred, succ;
    
    	<span class="hljs-comment">// 如果是在集合的末尾进行插入</span>
        <span class="hljs-keyword">if</span> (index == size) &#123;
            <span class="hljs-comment">// succ为空，pred为尾节点</span>
            succ = <span class="hljs-keyword">null</span>;
            pred = last;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-comment">// 如果不是在末尾进行插入, succ保存插入位置的节点，pred保存插入位置节点的前驱结点</span>
            succ = node(index);
            pred = succ.prev;
        &#125;

    	<span class="hljs-comment">// 使用增加for，通过迭代器顺序访问插入集合</span>
        <span class="hljs-keyword">for</span> (Object o : a) &#123;
            <span class="hljs-comment">// 将遍历的元素o赋值给变量e</span>
            <span class="hljs-meta">@SuppressWarnings</span>(<span class="hljs-string">"unchecked"</span>) E e = (E) o;
            
            <span class="hljs-comment">// 创建Node对象，Node为LinkedList的内部类。</span>
            <span class="hljs-comment">// 传入的值依次为：插入节点的前驱节点，该节点存储的数据，后继节点为null</span>
            Node&lt;E&gt; newNode = <span class="hljs-keyword">new</span> Node&lt;&gt;(pred, e, <span class="hljs-keyword">null</span>);
            
            <span class="hljs-comment">// 如果没有前驱节点，也就是在链表头部进行插入</span>
            <span class="hljs-keyword">if</span> (pred == <span class="hljs-keyword">null</span>)
                <span class="hljs-comment">// 该节点就是头结点</span>
                first = newNode;
            <span class="hljs-keyword">else</span>
                <span class="hljs-comment">// 如果有前驱结点，前驱结点就指向该节点</span>
                pred.next = newNode;
            <span class="hljs-comment">// 前驱节点后移，指向该节点</span>
            pred = newNode;
        &#125;
		
    	<span class="hljs-comment">// 如果是在尾部进行插入</span>
        <span class="hljs-keyword">if</span> (succ == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-comment">// pred节点就是尾节点</span>
            last = pred;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-comment">// 否则 pred 与 succ 互相指向对方</span>
            pred.next = succ;
            succ.prev = pred;
        &#125;
		
    	<span class="hljs-comment">// size扩大</span>
        size += numNew;
    
    	<span class="hljs-comment">// 修改次数+1</span>
        modCount++;
    
    	<span class="hljs-comment">// 返回修改成功</span>
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
&#125;


<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;
        E item;
        Node&lt;E&gt; next;
        Node&lt;E&gt; prev;
	
        Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) &#123;
            <span class="hljs-keyword">this</span>.item = element;
            <span class="hljs-keyword">this</span>.next = next;
            <span class="hljs-keyword">this</span>.prev = prev;
        &#125;
&#125;</code></pre>

<p>该构造函数先创建了一个空链表，然后调用了addAll()方法将待插入集合插入链表中</p>
<p><strong>图解插入过程：addAll()方法</strong></p>
<p><strong>情况一：在尾部插入</strong></p>
<ul>
<li>pred指向尾部的节点，succ指向null</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911214210.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>遍历待插入数组，取出第一个元素<ul>
<li>调用Node&lt;&gt;的构造方法，在初始化节点时，将其前驱结点赋值为pred节点</li>
<li>放在pred节点的后面，pred.next指向newNode。<strong>此时succ依然指向null</strong></li>
</ul>
</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911214251.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>pred后移，指向刚插入的节点</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911214321.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>重复上面的步骤，直到待插入集合中所有元素都插入到链表当中</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911214841.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>插入完毕后，因为succ为null，所以尾指针last变为pred</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911214948.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>情况二：在中间进行插入</strong></p>
<ul>
<li>在index=2处（第三个节点）处进行插入，succ保存了插入位置的节点，pred为其前驱节点</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911215148.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>在pred后面插入元素</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911215615.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>一直插入元素，直到插入完成</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911215732.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>如果succ不为空（指向了插入位置处的节点），pred的后继节点为succ，succ的前驱为pred</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911215943.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>可见，在LinkedList中间进行插入，是在index处节点之前进行插入操作的</strong></p>
<p><strong>情况三：在头部进行插入</strong></p>
<p>先使用头插法插入<strong>第一个元素</strong></p>
<ul>
<li>succ指向了头结点，pred指向其前驱，此时为null</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911220714.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>如果pred为空，则头指针 first 指向 newNode。<strong>让pred指向newNode</strong></li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911221015.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>然后<strong>在头结点之后插入剩余元素，因为此时的pred已经不为空了</strong></li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911221252.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>pred指向新插入的节点，此时待插入集合为空。pred 与 succ 互相指向对方。插入完毕</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200911221350.png" srcset="/img/loading.gif" alt=""></p>
<h3 id="2、添加方法-1"><a href="#2、添加方法-1" class="headerlink" title="2、添加方法"></a>2、添加方法</h3><h4 id="addFirst-E-e-方法"><a href="#addFirst-E-e-方法" class="headerlink" title="addFirst(E e)方法"></a>addFirst(E e)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addFirst</span><span class="hljs-params">(E e)</span> </span>&#123;
    	<span class="hljs-comment">// 调用linkFirst()方法</span>
        linkFirst(e);
&#125;

<span class="hljs-comment">// 私有方法，用头插法插入元素</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">linkFirst</span><span class="hljs-params">(E e)</span> </span>&#123;
    	<span class="hljs-comment">// 用 f 保存插入前链表中的头节点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; f = first;
    	
    	<span class="hljs-comment">// 创建一个新节点，值为待插入元素的值(e)， 后继节点为 f (插入前的头结点)</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; newNode = <span class="hljs-keyword">new</span> Node&lt;&gt;(<span class="hljs-keyword">null</span>, e, f);
    	
    	<span class="hljs-comment">// 头结点变为新插入的节点newNode</span>
        first = newNode;
    
    	<span class="hljs-comment">// 如果 f 为空，也就是插入前链表为空</span>
        <span class="hljs-keyword">if</span> (f == <span class="hljs-keyword">null</span>)
            <span class="hljs-comment">// newNode同时也是尾节点</span>
            last = newNode;
        <span class="hljs-keyword">else</span>
            <span class="hljs-comment">// 否则，newNode 为 f 的前驱结点</span>
            f.prev = newNode;
    
        size++;
        modCount++;
&#125;</code></pre>

<p>addFirst进行头插法插入元素时，会<strong>调用私有方法linkFirst来进行插入操作</strong></p>
<h4 id="addLast-E-e-方法"><a href="#addLast-E-e-方法" class="headerlink" title="addLast(E e)方法"></a>addLast(E e)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addLast</span><span class="hljs-params">(E e)</span> </span>&#123;
	<span class="hljs-comment">// 调用linkLast()方法来进行尾部插入</span>
    linkLast(e);
&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">linkLast</span><span class="hljs-params">(E e)</span> </span>&#123;
    	<span class="hljs-comment">// 用 l 来保存链表的尾节点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; l = last;
    
    	<span class="hljs-comment">// 创建新节点，值为待插入节点的值（e），前驱节点为l，也就是插入前的尾节点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; newNode = <span class="hljs-keyword">new</span> Node&lt;&gt;(l, e, <span class="hljs-keyword">null</span>);
    
    	<span class="hljs-comment">// newNode变为尾节点（last）</span>
        last = newNode;
    
    	<span class="hljs-comment">// 如果 l 为空，也就是插入前链表为空</span>
        <span class="hljs-keyword">if</span> (l == <span class="hljs-keyword">null</span>)
            <span class="hljs-comment">// newNode也是头结点</span>
            first = newNode;
        <span class="hljs-keyword">else</span>
            <span class="hljs-comment">// l的后继节点为newNode</span>
            l.next = newNode;
        size++;
        modCount++;
&#125;</code></pre>



<h4 id="add-E-e-方法-1"><a href="#add-E-e-方法-1" class="headerlink" title="add(E e)方法"></a>add(E e)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">add</span><span class="hljs-params">(E e)</span> </span>&#123;
    	<span class="hljs-comment">// 调用linkLast在末尾进行插入</span>
        linkLast(e);
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
&#125;</code></pre>



<h4 id="add-int-index-E-element-方法-1"><a href="#add-int-index-E-element-方法-1" class="headerlink" title="add(int index, E element)方法"></a>add(int index, E element)方法</h4><pre><code class="hljs axapta"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> add(<span class="hljs-keyword">int</span> <span class="hljs-keyword">index</span>, E element) &#123;
	<span class="hljs-comment">// 检查index是否越界</span>
    checkPositionIndex(<span class="hljs-keyword">index</span>);

	<span class="hljs-comment">// 如果 index == size，就在末尾进行插入</span>
    <span class="hljs-keyword">if</span> (<span class="hljs-keyword">index</span> == size)
        linkLast(element);
    <span class="hljs-keyword">else</span>
    	<span class="hljs-comment">// 否则就调用linkBefore()方法，在index处节点前进行插入</span>
    	<span class="hljs-comment">// 调用了node()方法，来获取指定索引出的元素</span>
        linkBefore(element, node(<span class="hljs-keyword">index</span>));
&#125;

Node&lt;E&gt; node(<span class="hljs-keyword">int</span> <span class="hljs-keyword">index</span>) &#123;
        <span class="hljs-comment">// assert isElementIndex(index);</span>
		<span class="hljs-comment">// 看index是在链表的前半段还是后半段</span>
        <span class="hljs-keyword">if</span> (<span class="hljs-keyword">index</span> &lt; (size &gt;&gt; <span class="hljs-number">1</span>)) &#123;
        	<span class="hljs-comment">// 如果是前半段，就通过first节点从前向后扫描</span>
            Node&lt;E&gt; x = first;
            
            <span class="hljs-comment">// 找到index处的元素并返回。0-&gt;index-1</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; <span class="hljs-keyword">index</span>; i++)
                x = x.next;
            <span class="hljs-keyword">return</span> x;
        &#125; <span class="hljs-keyword">else</span> &#123;
        	<span class="hljs-comment">// 否则，就通过last从后往前找</span>
            Node&lt;E&gt; x = last;
            
            <span class="hljs-comment">// 找到index的元素并返回。size-1 -&gt; index；</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = size - <span class="hljs-number">1</span>; i &gt; <span class="hljs-keyword">index</span>; i--)
                x = x.prev;
            <span class="hljs-keyword">return</span> x;
        &#125;
&#125;

<span class="hljs-comment">// e: 待插入节点</span>
<span class="hljs-comment">// succ: index位置上的节点</span>
<span class="hljs-keyword">void</span> linkBefore(E e, Node&lt;E&gt; succ) &#123;
        <span class="hljs-comment">// assert succ != null;</span>
    	<span class="hljs-comment">// 用pred为插入位置节点的前驱结点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; pred = succ.prev;
        
        <span class="hljs-comment">// 创建新节点，值为插入节点e，前驱结点为pred，后继为succ</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; newNode = <span class="hljs-keyword">new</span> Node&lt;&gt;(pred, e, succ);
        
        <span class="hljs-comment">// succ的前驱改为newNode，不再是pred</span>
        succ.prev = newNode;
        
        <span class="hljs-comment">// 如果pred为空，就是插入位置为链表头结点</span>
        <span class="hljs-keyword">if</span> (pred == <span class="hljs-keyword">null</span>)
        	<span class="hljs-comment">// newNode就是头结点</span>
            first = newNode;
        <span class="hljs-keyword">else</span>
        	<span class="hljs-comment">// 否则，pred的后继为newNode</span>
            pred.next = newNode;
            
        size++;
        modCount++;
&#125;</code></pre>



<h4 id="addAll-Collection-lt-extends-E-gt-c-方法-1"><a href="#addAll-Collection-lt-extends-E-gt-c-方法-1" class="headerlink" title="addAll(Collection&lt;? extends E&gt; c)方法"></a>addAll(Collection&lt;? extends E&gt; c)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">addAll</span><span class="hljs-params">(Collection&lt;? extends E&gt; c)</span> </span>&#123;
    <span class="hljs-comment">// 调用addAll(index, e)方法，也就是Collection构造函数时使用的那个方法</span>
    <span class="hljs-keyword">return</span> addAll(size, c);
&#125;</code></pre>



<h4 id="addAll-int-index-Collection-lt-extends-E-gt-c-方法-1"><a href="#addAll-int-index-Collection-lt-extends-E-gt-c-方法-1" class="headerlink" title="addAll(int index, Collection&lt;? extends E&gt; c)方法"></a>addAll(int index, Collection&lt;? extends E&gt; c)方法</h4><p>详见Collection构造函数调用 <a href="https://nyimac.gitee.io/2020/09/10/%E9%9B%86%E5%90%88%E6%BA%90%E7%A0%81/#Collection%E6%9E%84%E9%80%A0%E5%87%BD%E6%95%B0"><strong>addAll()方法</strong></a>时的分析 </p>
<h3 id="3、移除方法-1"><a href="#3、移除方法-1" class="headerlink" title="3、移除方法"></a>3、移除方法</h3><h4 id="remove-方法"><a href="#remove-方法" class="headerlink" title="remove()方法"></a>remove()方法</h4><p>remove()方法就是调用的removeFirst()方法，实际上是<strong>对removeFirst()及unlinkFirst()</strong>的解析</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">remove</span><span class="hljs-params">()</span> </span>&#123;
    <span class="hljs-comment">// 调用removeFirst()方法，移除链表首个元素</span>
    <span class="hljs-keyword">return</span> removeFirst();
&#125;


<span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">removeFirst</span><span class="hljs-params">()</span> </span>&#123;
    	<span class="hljs-comment">// 创建新节点f用于保存头结点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; f = first;
    	<span class="hljs-comment">// 如果头结点为空，也就是链表为空，抛出异常</span>
        <span class="hljs-keyword">if</span> (f == <span class="hljs-keyword">null</span>)
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NoSuchElementException();
    	<span class="hljs-comment">// 调用unlinkFirst()方法，并返回结果</span>
        <span class="hljs-keyword">return</span> unlinkFirst(f);
&#125;

<span class="hljs-function"><span class="hljs-keyword">private</span> E <span class="hljs-title">unlinkFirst</span><span class="hljs-params">(Node&lt;E&gt; f)</span> </span>&#123;
        <span class="hljs-comment">// assert f == first &amp;&amp; f != null;</span>
    	<span class="hljs-comment">// 创建element保存头结点的值，用于最后的返回</span>
        <span class="hljs-keyword">final</span> E element = f.item;
    
    	<span class="hljs-comment">// next保存头结点后面的一个节点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; next = f.next;
    	
    	<span class="hljs-comment">// 头结点的属性置空，方便回收</span>
        f.item = <span class="hljs-keyword">null</span>;
        f.next = <span class="hljs-keyword">null</span>; <span class="hljs-comment">// help GC</span>
    
    	<span class="hljs-comment">// 头指针first后移</span>
        first = next;
    
    	<span class="hljs-comment">// 如果链表只有一个节点</span>
        <span class="hljs-keyword">if</span> (next == <span class="hljs-keyword">null</span>)
            <span class="hljs-comment">// 尾指针为空</span>
            last = <span class="hljs-keyword">null</span>;
        <span class="hljs-keyword">else</span>
            <span class="hljs-comment">//否则，next的前驱结点为null（next现在是头结点）</span>
            next.prev = <span class="hljs-keyword">null</span>;
        size--;
        modCount++;
    
    	<span class="hljs-comment">// 返回被移除的节点的值</span>
        <span class="hljs-keyword">return</span> element;
&#125;</code></pre>



<h4 id="removeFirst-方法"><a href="#removeFirst-方法" class="headerlink" title="removeFirst()方法"></a>removeFirst()方法</h4><p>见remove()方法解析</p>
<h4 id="removeLast-方法"><a href="#removeLast-方法" class="headerlink" title="removeLast()方法"></a>removeLast()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">removeLast</span><span class="hljs-params">()</span> </span>&#123;
    	<span class="hljs-comment">// 创建新节点l保存尾节点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; l = last;
    	
    	<span class="hljs-comment">// 如果尾节点为空(链表为空)，就抛出异常</span>
        <span class="hljs-keyword">if</span> (l == <span class="hljs-keyword">null</span>)
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NoSuchElementException();
    
    	<span class="hljs-comment">// 返回unlinkLast()方法的返回结果</span>
        <span class="hljs-keyword">return</span> unlinkLast(l);
&#125;

<span class="hljs-comment">// 该方法和unlinkFirst方法类似，只不过是对尾节点进行删除操作</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> E <span class="hljs-title">unlinkLast</span><span class="hljs-params">(Node&lt;E&gt; l)</span> </span>&#123;
        <span class="hljs-comment">// assert l == last &amp;&amp; l != null;</span>
        <span class="hljs-keyword">final</span> E element = l.item;
        <span class="hljs-keyword">final</span> Node&lt;E&gt; prev = l.prev;
        l.item = <span class="hljs-keyword">null</span>;
        l.prev = <span class="hljs-keyword">null</span>; <span class="hljs-comment">// help GC</span>
        last = prev;
        <span class="hljs-keyword">if</span> (prev == <span class="hljs-keyword">null</span>)
            first = <span class="hljs-keyword">null</span>;
        <span class="hljs-keyword">else</span>
            prev.next = <span class="hljs-keyword">null</span>;
        size--;
        modCount++;
        <span class="hljs-keyword">return</span> element;
&#125;</code></pre>



<h4 id="remove-Object-o-方法-1"><a href="#remove-Object-o-方法-1" class="headerlink" title="remove(Object o)方法"></a>remove(Object o)方法</h4><p>移除<strong>首个</strong>遇到的指定元素</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">remove</span><span class="hljs-params">(Object o)</span> </span>&#123;
    	<span class="hljs-comment">// 如果要删除的元素为null</span>
        <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-comment">// 从头开始遍历链表</span>
            <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; x = x.next) &#123;
                <span class="hljs-comment">// 遇到节点值为null的，就调用unlink()方法执行删除操作</span>
                <span class="hljs-keyword">if</span> (x.item == <span class="hljs-keyword">null</span>) &#123;
                    unlink(x);
                    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
                &#125;
            &#125;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-comment">// 从头开始遍历链表 </span>
            <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; x = x.next) &#123;
                <span class="hljs-comment">// 如果是要删除的元素，就调用unlink()方法执行删除操作</span>
                <span class="hljs-keyword">if</span> (o.equals(x.item)) &#123;
                    unlink(x);
                    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
                &#125;
            &#125;
        &#125;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
&#125;

<span class="hljs-function">E <span class="hljs-title">unlink</span><span class="hljs-params">(Node&lt;E&gt; x)</span> </span>&#123;
        <span class="hljs-comment">// assert x != null;</span>
    	<span class="hljs-comment">// 保存被删除节点的值，用于返回</span>
        <span class="hljs-keyword">final</span> E element = x.item;
    
    	<span class="hljs-comment">// next节点用于保存被删除节点的后继节点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; next = x.next;
    
    	<span class="hljs-comment">// prev节点用于保存被删除节点的前驱结点</span>
        <span class="hljs-keyword">final</span> Node&lt;E&gt; prev = x.prev;

    	<span class="hljs-comment">// 如果前驱节点为null，即被删除的节点是头结点</span>
        <span class="hljs-keyword">if</span> (prev == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-comment">// 头指针指向被删除节点的下一个节点（next）</span>
            first = next;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-comment">// 否则，被删除节点的前驱结点指向其后继节点</span>
            prev.next = next;
            <span class="hljs-comment">// 被删除节点的前驱结点为null</span>
            x.prev = <span class="hljs-keyword">null</span>;
        &#125;

    	<span class="hljs-comment">// 如果没有后继节点，即被删除元素是链表的尾节点</span>
        <span class="hljs-keyword">if</span> (next == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-comment">// 尾指针指向被删除节点的前一个节点</span>
            last = prev;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-comment">// 否则，被删除节点的后继节点指向其前驱结点</span>
            next.prev = prev;
            
            <span class="hljs-comment">// 被删除节点的后继节点为null</span>
            x.next = <span class="hljs-keyword">null</span>;
        &#125;
		
    	<span class="hljs-comment">// 被删除节点的属性为null</span>
        x.item = <span class="hljs-keyword">null</span>;
        size--;
        modCount++;
        <span class="hljs-keyword">return</span> element;
&#125;</code></pre>



<p><strong>可以看到，unlinkFirst()、unlinkLast()和unlink()方法非常类似</strong>，都用于让某个节点从链表中<strong>移除</strong>的操作。只不过unlinkFirst和unlinkLast删除的是头、尾节点，实现相对简单。而unlink则是一个更完整的实现，可以删除链表中的任一元素</p>
<h4 id="remove-int-index-方法-1"><a href="#remove-int-index-方法-1" class="headerlink" title="remove(int index)方法"></a>remove(int index)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">remove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> index)</span> </span>&#123;
	<span class="hljs-comment">// 检查索引是否越界</span>
    checkElementIndex(index);
    
    <span class="hljs-comment">// 找到该位置的节点，调用unlink方法进行删除</span>
    <span class="hljs-keyword">return</span> unlink(node(index));
&#125;</code></pre>



<h4 id="removeFirstOccurrence-Object-o-方法"><a href="#removeFirstOccurrence-Object-o-方法" class="headerlink" title="removeFirstOccurrence(Object o)方法"></a>removeFirstOccurrence(Object o)方法</h4><p>该方法用于移除链表中<strong>第一次出现</strong>该元素的节点</p>
<pre><code class="hljs arduino"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">removeFirstOccurrence</span><span class="hljs-params">(Object o)</span> </span>&#123;
    <span class="hljs-keyword">return</span> <span class="hljs-built_in">remove</span>(o);
&#125;</code></pre>

<p>可以看出removeFirstOccurrence(Object o)方法其实就是调用的remove(Object o)方法，来进行链表首个指定元素的删除操作的</p>
<h4 id="removeLastOccurrence-Object-o-方法"><a href="#removeLastOccurrence-Object-o-方法" class="headerlink" title="removeLastOccurrence(Object o)方法"></a>removeLastOccurrence(Object o)方法</h4><p>该方法用于移除链表中<strong>最后一次出现</strong>该元素的节点</p>
<pre><code class="hljs gml">public boolean removeLastOccurrence(Object o) &#123;
	<span class="hljs-comment">// 从链表尾部进行查询，找到指定元素，删除后返回</span>
    <span class="hljs-keyword">if</span> (o == null) &#123;
        <span class="hljs-keyword">for</span> (Node&lt;E&gt; <span class="hljs-symbol">x</span> = last; <span class="hljs-symbol">x</span> != null; <span class="hljs-symbol">x</span> = <span class="hljs-symbol">x</span>.prev) &#123;
            <span class="hljs-keyword">if</span> (<span class="hljs-symbol">x</span>.item == null) &#123;
                unlink(<span class="hljs-symbol">x</span>);
                <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
            &#125;
        &#125;
    &#125; <span class="hljs-keyword">else</span> &#123;
        <span class="hljs-keyword">for</span> (Node&lt;E&gt; <span class="hljs-symbol">x</span> = last; <span class="hljs-symbol">x</span> != null; <span class="hljs-symbol">x</span> = <span class="hljs-symbol">x</span>.prev) &#123;
            <span class="hljs-keyword">if</span> (o.equals(<span class="hljs-symbol">x</span>.item)) &#123;
                unlink(<span class="hljs-symbol">x</span>);
                <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
            &#125;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
&#125;</code></pre>



<h3 id="4、迭代器"><a href="#4、迭代器" class="headerlink" title="4、迭代器"></a>4、迭代器</h3><pre><code class="hljs java"><span class="hljs-keyword">private</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ListItr</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">ListIterator</span>&lt;<span class="hljs-title">E</span>&gt; </span>&#123;
    <span class="hljs-keyword">private</span> Node&lt;E&gt; lastReturned;
    <span class="hljs-keyword">private</span> Node&lt;E&gt; next;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> nextIndex;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> expectedModCount = modCount;

    <span class="hljs-comment">// 构造方法，如果不传入index参数，则默认传入0</span>
    ListItr(<span class="hljs-keyword">int</span> index) &#123;
        <span class="hljs-comment">// assert isPositionIndex(index);</span>
        <span class="hljs-comment">// 给next和nextIndex赋值</span>
        next = (index == size) ? <span class="hljs-keyword">null</span> : node(index);
        nextIndex = index;
    &#125;
	
    <span class="hljs-comment">// 是否还有下一个元素</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">hasNext</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-comment">// 索引小于size则返回true</span>
        <span class="hljs-keyword">return</span> nextIndex &lt; size;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">next</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-comment">// 检查是否有并发问题，modeCount与expectedModCount是否相等</span>
        checkForComodification();
        
        <span class="hljs-comment">// 如果没有下一个元素了，就抛出异常</span>
        <span class="hljs-keyword">if</span> (!hasNext())
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NoSuchElementException();

        <span class="hljs-comment">// 用于返回的元素</span>
        lastReturned = next;
        
        <span class="hljs-comment">// 后移一位</span>
        next = next.next;
        
        <span class="hljs-comment">// 索引+1</span>
        nextIndex++;
        
        <span class="hljs-comment">// 返回元素的值</span>
        <span class="hljs-keyword">return</span> lastReturned.item;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">hasPrevious</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> nextIndex &gt; <span class="hljs-number">0</span>;
    &#125;

    
    <span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">checkForComodification</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">if</span> (modCount != expectedModCount)
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> ConcurrentModificationException();
    &#125;
&#125;</code></pre>



<p><strong>注意</strong>：使用迭代器遍历时，如果要删除，请<strong>使用迭代器中的remove()方法</strong>，而不要使用LinkedList实现的remove()方法。和<a href="https://nyimac.gitee.io/2020/09/10/%E9%9B%86%E5%90%88%E6%BA%90%E7%A0%81/#6%E3%80%81%E8%BF%AD%E4%BB%A3%E5%99%A8">ArrayList相似</a></p>
<h3 id="5、清空方法"><a href="#5、清空方法" class="headerlink" title="5、清空方法"></a>5、清空方法</h3><h4 id="clear-方法-1"><a href="#clear-方法-1" class="headerlink" title="clear()方法"></a>clear()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">clear</span><span class="hljs-params">()</span> </span>&#123;
    <span class="hljs-comment">// Clearing all of the links between nodes is "unnecessary", but:</span>
    <span class="hljs-comment">// - helps a generational GC if the discarded nodes inhabit</span>
    <span class="hljs-comment">//   more than one generation</span>
    <span class="hljs-comment">// - is sure to free memory even if there is a reachable Iterator</span>
    
    <span class="hljs-comment">// 从头节点开始遍历链表，将每个节点的每个属性都设置为null，以便于GC更彻底的清理</span>
    <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; ) &#123;
        Node&lt;E&gt; next = x.next;
        x.item = <span class="hljs-keyword">null</span>;
        x.next = <span class="hljs-keyword">null</span>;
        x.prev = <span class="hljs-keyword">null</span>;
        x = next;
    &#125;
    
    first = last = <span class="hljs-keyword">null</span>;
    size = <span class="hljs-number">0</span>;
    modCount++;
&#125;</code></pre>



<h3 id="6、包含方法"><a href="#6、包含方法" class="headerlink" title="6、包含方法"></a>6、包含方法</h3><h4 id="contains-Object-o-方法-1"><a href="#contains-Object-o-方法-1" class="headerlink" title="contains(Object o)方法"></a>contains(Object o)方法</h4><p>从头遍历，遇到需要查找的元素就<strong>返回其索引</strong>，然后<strong>根据其索引来判断是否有该元素</strong></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">contains</span><span class="hljs-params">(Object o)</span> </span>&#123;
    <span class="hljs-keyword">return</span> indexOf(o) != -<span class="hljs-number">1</span>;
&#125;

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">indexOf</span><span class="hljs-params">(Object o)</span> </span>&#123;
        <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; x = x.next) &#123;
                <span class="hljs-keyword">if</span> (x.item == <span class="hljs-keyword">null</span>)
                    <span class="hljs-keyword">return</span> index;
                index++;
            &#125;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-keyword">for</span> (Node&lt;E&gt; x = first; x != <span class="hljs-keyword">null</span>; x = x.next) &#123;
                <span class="hljs-keyword">if</span> (o.equals(x.item))
                    <span class="hljs-keyword">return</span> index;
                index++;
            &#125;
        &#125;
        <span class="hljs-keyword">return</span> -<span class="hljs-number">1</span>;
&#125;</code></pre>



<h4 id="区分node-indexOf-和lastIndexOf-方法"><a href="#区分node-indexOf-和lastIndexOf-方法" class="headerlink" title="区分node(), indexOf()和lastIndexOf()方法"></a>区分node(), indexOf()和lastIndexOf()方法</h4><p>相同点</p>
<ul>
<li>这三个方法都用于查找</li>
</ul>
<p>不同点</p>
<ul>
<li>node(index)方法是用来<strong>返回指定索引处的节点的</strong></li>
<li>indexOf(o)是用来返回<strong>第一次</strong>遇到o时，<strong>节点的索引</strong>（从前往后找）</li>
<li>lastIndexOf(o)是用来返回<strong>最后一次</strong>遇到o时，<strong>节点的索引</strong>（从后往前找）</li>
</ul>
<h4 id=""><a href="#" class="headerlink" title=""></a></h4><h1 id="HashMap"><a href="#HashMap" class="headerlink" title="HashMap"></a>HashMap</h1><p>参考<a href="https://www.bilibili.com/video/BV18E411C7kD?from=search&seid=7736271791290237476" target="_blank" rel="noopener"><strong>Java 7/8 HashMap源码详解与面试题分析</strong></a></p>
<h2 id="一、哈希表简介"><a href="#一、哈希表简介" class="headerlink" title="一、哈希表简介"></a>一、哈希表简介</h2><p>可以参考<a href="https://nyimac.gitee.io/2020/06/17/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/#%E4%B8%83%E3%80%81%E5%93%88%E5%B8%8C%E8%A1%A8"><strong>Java数据结构与算法——哈希表</strong></a></p>
<ul>
<li>核心是基于哈希值的<strong>桶和链表</strong><ul>
<li>一般用数组实现桶</li>
<li>发生哈希碰撞时，用链表来链接发生碰撞的元素</li>
</ul>
</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200912171718.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>O(1)的平均查找、插入、删除时间</li>
<li>致命缺点是<strong>哈希值的碰撞</strong>(collision)<ul>
<li>哈希碰撞：元素通过哈希函数计算后，被映射到同一个桶中。例如上图中的桶1, 5中的元素就发生了哈希碰撞</li>
</ul>
</li>
</ul>
<h2 id="二、继承关系"><a href="#二、继承关系" class="headerlink" title="二、继承关系"></a>二、继承关系</h2><p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200912194932.png" srcset="/img/loading.gif" alt=""></p>
<h2 id="三、Java-7-HashMap"><a href="#三、Java-7-HashMap" class="headerlink" title="三、Java 7 HashMap"></a>三、Java 7 HashMap</h2><p><strong>这里只针对 Java 7 中不足的地方做简单分析</strong></p>
<h3 id="1、构造方法-2"><a href="#1、构造方法-2" class="headerlink" title="1、构造方法"></a>1、构造方法</h3><h4 id="无参构造方法-1"><a href="#无参构造方法-1" class="headerlink" title="无参构造方法"></a>无参构造方法</h4><pre><code class="hljs java"><span class="hljs-comment">// 默认初始化容量 2^4 = 16</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">4</span>; <span class="hljs-comment">// aka 16</span>

<span class="hljs-comment">// 最大容量</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MAXIMUM_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">30</span>;

<span class="hljs-comment">// 默认负载因子 0.75，用于计算阈值，进行扩容操作。选择0.75是一种在时间和空间上的折中选择 </span>
<span class="hljs-comment">// 如果当前哈希表中的元素个数 &gt;= 容量 × 负载因子，就会进行扩容，否则可能就会发生严重的哈希碰撞</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="hljs-number">0.75f</span>;

<span class="hljs-comment">// 此处调用了含容量和负载因子的构造方法来进行初始化操作</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">this</span>(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
&#125;</code></pre>



<h4 id="含容量的构造方法"><a href="#含容量的构造方法" class="headerlink" title="含容量的构造方法"></a>含容量的构造方法</h4><pre><code class="hljs java"> <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;
 		<span class="hljs-comment">// 调用了含容量和负载因子的构造方法来进行初始化操作，其中容量为传入的容量，负载因子为默认负载因子0.75</span>
        <span class="hljs-keyword">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);
&#125;</code></pre>



<h4 id="含容量和负载因子的构造方法"><a href="#含容量和负载因子的构造方法" class="headerlink" title="含容量和负载因子的构造方法"></a>含容量和负载因子的构造方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity, <span class="hljs-keyword">float</span> loadFactor)</span> </span>&#123;
    	<span class="hljs-comment">// 如果传入的初始化容量小于0，则抛出异常</span>
        <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">0</span>)
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">"Illegal initial capacity: "</span> +
                                               initialCapacity);
    
    	<span class="hljs-comment">// 如果传入的容量大于最大容量，就初始化为最大容量</span>
        <span class="hljs-keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
    
    	<span class="hljs-comment">// 如果负载因子小于0，或者是非法的浮点数，抛出异常</span>
        <span class="hljs-keyword">if</span> (loadFactor &lt;= <span class="hljs-number">0</span> || Float.isNaN(loadFactor))
            <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">"Illegal load factor: "</span> +
                                               loadFactor);
    
    
		<span class="hljs-comment">// 根据传入的负载因子给负载因子赋值</span>
        <span class="hljs-keyword">this</span>.loadFactor = loadFactor;
   
    	<span class="hljs-comment">// int threshold</span>
    	<span class="hljs-comment">// 阈值，容量×负载因子。目前大小为initialCapacity（还未扩容）</span>
    	<span class="hljs-comment">// 超过阈值进行扩容操作</span>
        threshold = initialCapacity;
    
    	<span class="hljs-comment">// 此处的init()方法是一个空方法，在向哈希表添加元素之前，不会真正地创建哈希表（以免占用过多的内存）</span>
        init();
&#125;

<span class="hljs-comment">// 空方法</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">init</span><span class="hljs-params">()</span> </span>&#123;
&#125;</code></pre>



<p>可见，无论调用哪种构造函数来初始化HashMap，最终调用的都是<strong>含容量和负载因子的构造方法</strong>，并且都<strong>没有真正的开辟出需要的内存空间</strong></p>
<h3 id="2、添加方法-2"><a href="#2、添加方法-2" class="headerlink" title="2、添加方法"></a>2、添加方法</h3><h4 id="put-方法"><a href="#put-方法" class="headerlink" title="put()方法"></a>put()方法</h4><pre><code class="hljs java"><span class="hljs-comment">// 空集合，用于判断表是否为空。Entry为hashMap的静态内部类</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> Entry&lt;?,?&gt;[] EMPTY_TABLE = &#123;&#125;;

<span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>&#123;
    <span class="hljs-comment">// 如果表是空的，就通过inflateTable()方法进行扩容</span>
    <span class="hljs-keyword">if</span> (table == EMPTY_TABLE) &#123;
        <span class="hljs-comment">// 等到真正向哈希表中添加元素时，才开辟内存空间</span>
        inflateTable(threshold);
    &#125;
    
    <span class="hljs-keyword">if</span> (key == <span class="hljs-keyword">null</span>)
        <span class="hljs-keyword">return</span> putForNullKey(value);
    
    <span class="hljs-comment">// 计算要插入元素的哈希值</span>
    <span class="hljs-keyword">int</span> hash = hash(key);
    
    <span class="hljs-comment">// 根据哈希值来判断插入元素应该放在哪个桶中</span>
    <span class="hljs-comment">// 该方法决定了为什么哈希表的容量是2的幂</span>
    <span class="hljs-keyword">int</span> i = indexFor(hash, table.length);
    
    <span class="hljs-comment">// 遍历哈希表</span>
    <span class="hljs-keyword">for</span> (Entry&lt;K,V&gt; e = table[i]; e != <span class="hljs-keyword">null</span>; e = e.next) &#123;
        Object k;
        
        <span class="hljs-comment">// 看待插入元素在哈希表中是否已近存在了，如果存在了，就进行覆盖操作</span>
        <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) &#123;
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(<span class="hljs-keyword">this</span>);
            <span class="hljs-keyword">return</span> oldValue;
        &#125;
    &#125;

    modCount++;
    
   	<span class="hljs-comment">// 真正的添加操作，采用头插法，下面会单独来说</span>
    addEntry(hash, key, value, i);
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
&#125;


<span class="hljs-comment">// 哈希表扩容函数</span>
<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">inflateTable</span><span class="hljs-params">(<span class="hljs-keyword">int</span> toSize)</span> </span>&#123;
        <span class="hljs-comment">// Find a power of 2 &gt;= toSize</span>
    	<span class="hljs-comment">// 让容量向上舍入变为2的幂。比如toSize = 10 就会变为 16。</span>
        <span class="hljs-keyword">int</span> capacity = roundUpToPowerOf2(toSize);
		
    	<span class="hljs-comment">// 阈值，向上取整后的容量×负载因子 或 最大容量+1，取其中的较小值</span>
    	<span class="hljs-comment">// 该变量在第一次放入操作时不会用到</span>
        threshold = (<span class="hljs-keyword">int</span>) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + <span class="hljs-number">1</span>);
    
    	<span class="hljs-comment">// 根据capacity创建哈希表</span>
        table = <span class="hljs-keyword">new</span> Entry[capacity];
     	
    	<span class="hljs-comment">// 创建了一个哈希种子，重构String的hash算法，在后面的潜在安全漏洞会谈到</span>
        initHashSeedAsNeeded(capacity);
&#125;

<span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">roundUpToPowerOf2</span><span class="hljs-params">(<span class="hljs-keyword">int</span> number)</span> </span>&#123;
        <span class="hljs-comment">// assert number &gt;= 0 : "number must be non-negative";</span>
    	<span class="hljs-comment">// 如果容量大于最大容量，就返回最大容量。</span>
    	<span class="hljs-comment">// 否则调用Integer.highestOneBit()方法让其向上舍入为2的幂</span>
        <span class="hljs-keyword">return</span> number &gt;= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number &gt; <span class="hljs-number">1</span>) ? Integer.highestOneBit((number - <span class="hljs-number">1</span>) &lt;&lt; <span class="hljs-number">1</span>) : <span class="hljs-number">1</span>;
&#125;

<span class="hljs-comment">// 通过一系列移位操作与异或操作获得元素的哈希值。 JDK 8 中已不再使用该方法</span>
<span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hash</span><span class="hljs-params">(Object k)</span> </span>&#123;
        <span class="hljs-keyword">int</span> h = hashSeed;
    	<span class="hljs-comment">// 如果哈希种子存在，并且进行哈希的元素的String类型</span>
        <span class="hljs-keyword">if</span> (<span class="hljs-number">0</span> != h &amp;&amp; k <span class="hljs-keyword">instanceof</span> String) &#123;
            <span class="hljs-comment">// 就让String使用另一种hash算法</span>
            <span class="hljs-keyword">return</span> sun.misc.Hashing.stringHash32((String) k);
        &#125;

        h ^= k.hashCode();

        <span class="hljs-comment">// This function ensures that hashCodes that differ only by</span>
        <span class="hljs-comment">// constant multiples at each bit position have a bounded</span>
        <span class="hljs-comment">// number of collisions (approximately 8 at default load factor).</span>
        h ^= (h &gt;&gt;&gt; <span class="hljs-number">20</span>) ^ (h &gt;&gt;&gt; <span class="hljs-number">12</span>);
        <span class="hljs-keyword">return</span> h ^ (h &gt;&gt;&gt; <span class="hljs-number">7</span>) ^ (h &gt;&gt;&gt; <span class="hljs-number">4</span>);
&#125;</code></pre>



<h4 id="为什么哈希表大小一定是2的幂？"><a href="#为什么哈希表大小一定是2的幂？" class="headerlink" title="为什么哈希表大小一定是2的幂？"></a>为什么哈希表大小一定是2的幂？</h4><p>要回答这个问题，我们需要先看看哈希表中一个重要的方法：<strong>static int indexFor(int h, int length)</strong>，该方法会根据插入元素的哈希值<strong>决定该元素应该被放在桶中</strong></p>
<pre><code class="hljs cpp"><span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">indexFor</span><span class="hljs-params">(<span class="hljs-keyword">int</span> h, <span class="hljs-keyword">int</span> length)</span> </span>&#123;
        <span class="hljs-comment">// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";</span>
        <span class="hljs-comment">// 将传入的哈希值与其长度-1进行按位与操作，并返回其结果</span>
        <span class="hljs-keyword">return</span> h &amp; (length<span class="hljs-number">-1</span>);
&#125;</code></pre>

<p>我们知道，哈希表的致命缺点是发生<strong>哈希碰撞</strong>，也就是<strong>多个哈希值相同的元素被放置到了同一个桶中</strong></p>
<p>想要尽量避免发生哈希碰撞，分别分到不同的桶中，<strong>h &amp; (length-1)</strong> 就是这样一个操作，<strong>根据元素的哈希值和哈希表的长度-1来按位与</strong>，并且与运算的速度快，效率高</p>
<p>当哈希表的大小为2的幂时，我们拿16来举例，它的二进制表示是 <strong>10000</strong> ， 让其<strong>长度-1</strong>后就是 <strong>1111</strong>，全部都是1</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200912201609.png" srcset="/img/loading.gif" alt=""></p>
<p>我们知道，当<strong>一个二进制数与全为1的数进行按位与时，其结果就是该数本身并且小于等于桶的最大数量</strong>。这样一来，只要数不同，那么他们按位与下来的值也就不同了，所以我们需要哈希表的容量为2的幂</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200912201909.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>为什么使用位运算，而不是直接取模？</strong></p>
<p><strong>位运算(&amp;)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。</strong></p>
<h4 id="addEntry-方法"><a href="#addEntry-方法" class="headerlink" title="addEntry()方法"></a>addEntry()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">addEntry</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">int</span> bucketIndex)</span> </span>&#123;
    <span class="hljs-comment">// 如果哈希表中的元素个数超过了阈值，并且该元素应该放入的桶中已经有了元素</span>
    <span class="hljs-keyword">if</span> ((size &gt;= threshold) &amp;&amp; (<span class="hljs-keyword">null</span> != table[bucketIndex])) &#123;
        <span class="hljs-comment">// 进行扩容，扩容大小为原大小的2倍，以保证扩容后容量仍为2的幂</span>
        <span class="hljs-comment">// 并将扩容前哈希表中的元素全部重新计算哈希值，并放入到扩容后的桶中</span>
        resize(<span class="hljs-number">2</span> * table.length);
        
        <span class="hljs-comment">// 重新计算哈希值</span>
        hash = (<span class="hljs-keyword">null</span> != key) ? hash(key) : <span class="hljs-number">0</span>;
        bucketIndex = indexFor(hash, table.length);
    &#125;

    <span class="hljs-comment">// 创建节点，采用头插法将其放在对应的桶中</span>
    createEntry(hash, key, value, bucketIndex);
&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">resize</span><span class="hljs-params">(<span class="hljs-keyword">int</span> newCapacity)</span> </span>&#123;
        Entry[] oldTable = table;
        <span class="hljs-keyword">int</span> oldCapacity = oldTable.length;
        <span class="hljs-keyword">if</span> (oldCapacity == MAXIMUM_CAPACITY) &#123;
            threshold = Integer.MAX_VALUE;
            <span class="hljs-keyword">return</span>;
        &#125;
		
    	<span class="hljs-comment">// 扩容为新容量</span>
        Entry[] newTable = <span class="hljs-keyword">new</span> Entry[newCapacity];
    
    	<span class="hljs-comment">// 重新计算元素哈希值，再放入到扩容后的哈希表中</span>
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
    
    	<span class="hljs-comment">//重新计算阈值</span>
        threshold = (<span class="hljs-keyword">int</span>)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + <span class="hljs-number">1</span>);
&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">transfer</span><span class="hljs-params">(Entry[] newTable, <span class="hljs-keyword">boolean</span> rehash)</span> </span>&#123;
        <span class="hljs-keyword">int</span> newCapacity = newTable.length;
    
    	<span class="hljs-comment">// 遍历原来哈希表中的元素</span>
        <span class="hljs-keyword">for</span> (Entry&lt;K,V&gt; e : table) &#123;
            <span class="hljs-comment">// 如果桶中元素不为空，就重新计算起哈希值，然后放入到扩容后的哈希表中</span>
            <span class="hljs-keyword">while</span>(<span class="hljs-keyword">null</span> != e) &#123;
                Entry&lt;K,V&gt; next = e.next;
                <span class="hljs-keyword">if</span> (rehash) &#123;
                    e.hash = <span class="hljs-keyword">null</span> == e.key ? <span class="hljs-number">0</span> : hash(e.key);
                &#125;
                <span class="hljs-keyword">int</span> i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                
                <span class="hljs-comment">// 扩容转移时使用头插法</span>
                newTable[i] = e;
                e = next;
            &#125;
        &#125;
&#125;

<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">createEntry</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">int</span> bucketIndex)</span> </span>&#123;
        Entry&lt;K,V&gt; e = table[bucketIndex];
    	
    	<span class="hljs-comment">// 将新节点放在桶的第一个位置，也就是采用头插法进行插入</span>
    	<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">createEntry</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">int</span> bucketIndex)</span> </span>&#123;
        Entry&lt;K,V&gt; e = table[bucketIndex];
        table[bucketIndex] = <span class="hljs-keyword">new</span> Entry&lt;&gt;(hash, key, value, e);
        size++;
    &#125;
        table[bucketIndex] = <span class="hljs-keyword">new</span> Entry&lt;&gt;(hash, key, value, e);
        size++;
&#125;</code></pre>



<h3 id="3、存在的问题"><a href="#3、存在的问题" class="headerlink" title="3、存在的问题"></a>3、存在的问题</h3><h4 id="容易发生死锁"><a href="#容易发生死锁" class="headerlink" title="容易发生死锁"></a>容易发生死锁</h4><p>因为HashMap本身是<strong>线程不安全</strong>的，所以在多线程环境下，可能会发生死锁问题</p>
<p>参考<a href="https://coolshell.cn/articles/9606.html" target="_blank" rel="noopener"><strong>疫苗：Java HashMap的死循环</strong></a></p>
<h4 id="潜在的安全漏洞"><a href="#潜在的安全漏洞" class="headerlink" title="潜在的安全漏洞"></a>潜在的安全漏洞</h4><p>哈希碰撞可能使哈希表<strong>退化为链表</strong>，链表的查询效率低，一旦退话，将会严重拖慢我们程序的性能</p>
<p>String的哈希算法<strong>很容易就能产生多个哈希值相同字符串</strong></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hashCode</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">int</span> h = hash;
        <span class="hljs-keyword">if</span> (h == <span class="hljs-number">0</span> &amp;&amp; value.length &gt; <span class="hljs-number">0</span>) &#123;
            <span class="hljs-keyword">char</span> val[] = value;

            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; value.length; i++) &#123;
                h = <span class="hljs-number">31</span> * h + val[i];
            &#125;
            hash = h;
        &#125;
        <span class="hljs-keyword">return</span> h;
&#125;</code></pre>

<p>黑客可以在url中携带多个哈希值一样的字符串，来访问我们的服务器，此时因为所有字符串的哈希值相同，所以都会被放到同一个桶中，使得哈希表退化为链表，大幅度降低我们的性能。为了避免这种攻击，<strong>在 JDK 7 的哈希表中，重构了String类型计算哈希值的方法</strong></p>
<h2 id="四、Java-8-HashMap"><a href="#四、Java-8-HashMap" class="headerlink" title="四、Java 8 HashMap"></a>四、Java 8 HashMap</h2><h3 id="1、红黑树TreeMap"><a href="#1、红黑树TreeMap" class="headerlink" title="1、红黑树TreeMap"></a>1、红黑树TreeMap</h3><h4 id="基本介绍"><a href="#基本介绍" class="headerlink" title="基本介绍"></a>基本介绍</h4><p>一种<strong>二叉查找树</strong>，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（<strong>非红即黑</strong>）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保<strong>没有一条路径会比其它路径长出两倍</strong>，因此，红黑树是一种<strong>弱平衡二叉树</strong>（由于是弱平衡，可以看到，<strong>在相同的节点情况下，AVL树的高度低于红黑树）</strong>，相对于要求严格的AVL树来说，它的旋转次数少，所以<strong>对于搜索，插入，删除操作较多的情况下，我们就用红黑树</strong></p>
<h4 id="性质"><a href="#性质" class="headerlink" title="性质"></a>性质</h4><ul>
<li>每个节点非红即黑</li>
<li>根节点（root）是黑的</li>
<li><strong>不能有两个红色的节点连在一起</strong>（黑色可以）</li>
<li>每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的</li>
<li>如果一个节点是红的，那么它的两儿子都是黑的</li>
<li>对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点</li>
<li>每条路径<strong>都包含相同的黑节点</strong></li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913110321.png" srcset="/img/loading.gif" alt=""></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913163158.png" srcset="/img/loading.gif" alt=""></p>
<h4 id="为什么用到了红黑树"><a href="#为什么用到了红黑树" class="headerlink" title="为什么用到了红黑树"></a>为什么用到了红黑树</h4><p>让我们来看看注释</p>
<pre><code class="hljs java"><span class="hljs-comment">/*</span>
<span class="hljs-comment">HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表</span>
<span class="hljs-comment">    实现注意事项。</span>
<span class="hljs-comment">    链表结构（这里叫 bin ，箱子）</span>
<span class="hljs-comment">    Map通常充当一个binned（桶）的哈希表，但是当箱子变得太大时，它们就会被转换成TreeNodes的箱子，每个箱子的结构都类似于java.util.TreeMap。</span>
<span class="hljs-comment">    大多数方法都尝试使用普通的垃圾箱，但是在适用的情况下（只要检查一个节点的实例）就可以传递到TreeNode方法。</span>
<span class="hljs-comment">    可以像其他的一样遍历和使用TreeNodes，但是在过度填充的时候支持更快的查找</span>
<span class="hljs-comment">    然而，由于大多数正常使用的箱子没有过多的填充，所以在表方法的过程中，检查树箱的存在可能会被延迟。</span>
<span class="hljs-comment">    树箱(bins即所有的元素都是TreeNodes）主要是由hashCode来排序的，但是在特定的情况下，</span>
<span class="hljs-comment">    如果两个元素是相同的“实现了Comparable接口”，那么使用它们的比较方法排序。</span>
<span class="hljs-comment">    （我们通过反射来保守地检查泛型类型，以验证这一点——参见方法comparableClassFor）。</span>
<span class="hljs-comment">    使用树带来的额外复杂，是非常有价值的，因为能提供了最坏只有O(log n)的时间复杂度当键有不同的散列或可排序。</span>
<span class="hljs-comment">    因此,性能降低优雅地在意外或恶意使用hashCode()返回值的分布很差,以及许多key共享一个hashCode,只要他们是可比较的。</span>
<span class="hljs-comment">    （如果这两种方法都不适用，同时不采取任何预防措施，我们可能会在时间和空间上浪费大约两倍的时间。</span>
<span class="hljs-comment">    但是，唯一已知的案例源于糟糕的用户编程实践，这些实践已经非常缓慢，这几乎没有什么区别。）</span>
<span class="hljs-comment">    因为TreeNodes大小大约是普通节点的两倍，所以只有当容器包含足够的节点来保证使用时才使用它们（见treeifythreshold）。</span>
<span class="hljs-comment">    当它们变得太小（由于移除或调整大小），它们就会被转换回普通bins。</span>
<span class="hljs-comment">    在使用良好的用户hashcode的用法中，很少使用树箱。</span>
<span class="hljs-comment">    理想情况下，在随机的hashcode中，箱子中节点的频率遵循泊松分布（http://en.wikipedia.org/wiki/Poisson_distribution），</span>
<span class="hljs-comment">    默认大小调整阈值为0.75，但由于调整粒度的大小有很大的差异。</span>
<span class="hljs-comment">    忽略方差，list的长度 k=(exp(-0.5) * pow(0.5, k) / factorial(k))</span>
<span class="hljs-comment">    第一个值是:</span>
<span class="hljs-comment">            0:0.60653066</span>
<span class="hljs-comment">            1:0.30326533</span>
<span class="hljs-comment">            2:0.07581633</span>
<span class="hljs-comment">            3:0.01263606</span>
<span class="hljs-comment">            4:0.00157952</span>
<span class="hljs-comment">            5:0.00015795</span>
<span class="hljs-comment">            6:0.00001316</span>
<span class="hljs-comment">            7:0.00000094</span>
<span class="hljs-comment">            8:0.00000006</span>
<span class="hljs-comment">    more: less than 1 in ten million 如果再多的话，概率就小于十万分之一了</span>
<span class="hljs-comment">    树箱（tree bin很难翻译啊！）的根通常是它的第一个节点。</span>
<span class="hljs-comment">    然而，有时（目前只在Iterator.remove）中，根可能在其他地方，但是可以通过父链接（方法TreeNode.root()）恢复。</span>
<span class="hljs-comment">    所有适用的内部方法都接受散列码作为参数（通常由公共方法提供），允许它们在不重新计算用户hashcode的情况下调用彼此。</span>
<span class="hljs-comment">    大多数内部方法也接受一个“标签”参数，通常是当前表，但在调整或转换时可能是新的或旧的。</span>
<span class="hljs-comment">    当bin列表被树化、分割或取消时（ treeified, split, or untreeified），我们将它们保持在相同的相对存取/遍历顺序（例如</span>
<span class="hljs-comment">    字段Node.next）为了更好地保存位置，并稍微简化对调用迭代器的拆分和traversals的处理(splits and traversals that invoke iterator.remove)。</span>
<span class="hljs-comment">    当在插入中使用比较器时，为了在重新平衡中保持一个总排序（或者在这里需要的接近），我们将类和标识符码作为连接开关。</span>
<span class="hljs-comment">    由于子类LinkedHashMap的存在，普通(plain)与树模型(tree modes)之间的使用和转换变得复杂起来。</span>
<span class="hljs-comment">    请参阅下面的hook方法，这些方法在插入、删除和访问时被调用，允许LinkedHashMap内部结构保持独立于这些机制。</span>
<span class="hljs-comment">            （这还要求将Map实例传递给一些可能创建新节点的实用方法。）</span>
<span class="hljs-comment">    concurrent-programming-like SSA-based编码风格有助于避免在所有扭曲的指针操作中出现混叠错误。</span>
<span class="hljs-comment">*/</span></code></pre>

<p>之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历<strong>查找会非常慢</strong></p>
<p>而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了<strong>查找数据快</strong>O(log n)，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当<strong>桶中元素大于8并且桶的个数大于64</strong>的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢</p>
<p>链表转红黑树体现了<strong>空间换时间</strong>的思想</p>
<h3 id="2、属性"><a href="#2、属性" class="headerlink" title="2、属性"></a>2、属性</h3><pre><code class="hljs java"><span class="hljs-comment">// 初始容量 16 (2的4次方)</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">4</span>; <span class="hljs-comment">// aka 16</span>

<span class="hljs-comment">// 最大容量</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MAXIMUM_CAPACITY = <span class="hljs-number">1</span> &lt;&lt; <span class="hljs-number">30</span>;

<span class="hljs-comment">// 默认负载因子，默认为0.75，用于和容量一起决定扩容的阈值</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="hljs-number">0.75f</span>;

<span class="hljs-comment">// 使用红黑树的阈值，当桶中的元素个数（链表长度）大于8时，才会使用红黑树进行存储</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> TREEIFY_THRESHOLD = <span class="hljs-number">8</span>;

<span class="hljs-comment">// 使用链表的阈值，当桶中的元素个数小于6个时，就会由红黑树转变为链表</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> UNTREEIFY_THRESHOLD = <span class="hljs-number">6</span>;

<span class="hljs-comment">// 最小的红黑树化的桶数，当桶的个数大于64个时，就会使用红黑树进行存储</span>
<span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> MIN_TREEIFY_CAPACITY = <span class="hljs-number">64</span>;

<span class="hljs-comment">// Node数组，也就是桶</span>
<span class="hljs-keyword">transient</span> Node&lt;K, V&gt;[] table;


<span class="hljs-comment">// 缓存entrySet</span>
<span class="hljs-keyword">transient</span> Set&lt;Map.Entry&lt;K,V&gt;&gt; entrySet;

<span class="hljs-comment">// map中k-v键值对的个数</span>
<span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> size;

<span class="hljs-comment">// 修改访问标记</span>
<span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> modCount;

<span class="hljs-comment">// 扩容阈值，等于 容量 × 负载因子，初始化时值为向上取2的幂</span>
<span class="hljs-keyword">int</span> threshold;

<span class="hljs-comment">// 负载因子</span>
<span class="hljs-keyword">final</span> <span class="hljs-keyword">float</span> loadFactor;</code></pre>





<h3 id="3、存储结构"><a href="#3、存储结构" class="headerlink" title="3、存储结构"></a>3、存储结构</h3><pre><code class="hljs java"><span class="hljs-keyword">static</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span>&lt;<span class="hljs-title">K</span>,<span class="hljs-title">V</span>&gt; <span class="hljs-keyword">implements</span> <span class="hljs-title">Map</span>.<span class="hljs-title">Entry</span>&lt;<span class="hljs-title">K</span>,<span class="hljs-title">V</span>&gt; </span>&#123;
    <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> hash;
    <span class="hljs-keyword">final</span> K key;
    V value;
    Node&lt;K,V&gt; next;

    Node(<span class="hljs-keyword">int</span> hash, K key, V value, Node&lt;K,V&gt; next) &#123;
        <span class="hljs-keyword">this</span>.hash = hash;
        <span class="hljs-keyword">this</span>.key = key;
        <span class="hljs-keyword">this</span>.value = value;
        <span class="hljs-keyword">this</span>.next = next;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> K <span class="hljs-title">getKey</span><span class="hljs-params">()</span>        </span>&#123; <span class="hljs-keyword">return</span> key; &#125;
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> V <span class="hljs-title">getValue</span><span class="hljs-params">()</span>      </span>&#123; <span class="hljs-keyword">return</span> value; &#125;
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123; <span class="hljs-keyword">return</span> key + <span class="hljs-string">"="</span> + value; &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hashCode</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> Objects.hashCode(key) ^ Objects.hashCode(value);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> V <span class="hljs-title">setValue</span><span class="hljs-params">(V newValue)</span> </span>&#123;
        V oldValue = value;
        value = newValue;
        <span class="hljs-keyword">return</span> oldValue;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">equals</span><span class="hljs-params">(Object o)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (o == <span class="hljs-keyword">this</span>)
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
        <span class="hljs-keyword">if</span> (o <span class="hljs-keyword">instanceof</span> Map.Entry) &#123;
            Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;
            <span class="hljs-keyword">if</span> (Objects.equals(key, e.getKey()) &amp;&amp;
                Objects.equals(value, e.getValue()))
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
        &#125;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    &#125;
&#125;</code></pre>



<h3 id="4、构造方法"><a href="#4、构造方法" class="headerlink" title="4、构造方法"></a>4、构造方法</h3><h4 id="无参构造方法-2"><a href="#无参构造方法-2" class="headerlink" title="无参构造方法"></a>无参构造方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">()</span> </span>&#123;
    <span class="hljs-comment">// 初始化了负载因子</span>
    <span class="hljs-keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR; <span class="hljs-comment">// all other fields defaulted</span>
&#125;</code></pre>



<h4 id="HashMap-int-initialCapacity-构造方法"><a href="#HashMap-int-initialCapacity-构造方法" class="headerlink" title="HashMap(int initialCapacity)构造方法"></a>HashMap(int initialCapacity)构造方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;
    <span class="hljs-keyword">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);
&#125;</code></pre>



<h4 id="HashMap-int-initialCapacity-float-loadFactor-方法"><a href="#HashMap-int-initialCapacity-float-loadFactor-方法" class="headerlink" title="HashMap(int initialCapacity, float loadFactor)方法"></a>HashMap(int initialCapacity, float loadFactor)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">HashMap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity, <span class="hljs-keyword">float</span> loadFactor)</span> </span>&#123;
    <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">0</span>)
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">"Illegal initial capacity: "</span> +
                                           initialCapacity);
    <span class="hljs-keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    <span class="hljs-keyword">if</span> (loadFactor &lt;= <span class="hljs-number">0</span> || Float.isNaN(loadFactor))
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException(<span class="hljs-string">"Illegal load factor: "</span> +
                                           loadFactor);
    <span class="hljs-keyword">this</span>.loadFactor = loadFactor;
    
    <span class="hljs-comment">// 阈值，初始化时为传入容量取幂后的值</span>
    <span class="hljs-keyword">this</span>.threshold = tableSizeFor(initialCapacity);
&#125;

<span class="hljs-comment">// 容量向上取整为2的幂</span>
<span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">tableSizeFor</span><span class="hljs-params">(<span class="hljs-keyword">int</span> cap)</span> </span>&#123;
        <span class="hljs-keyword">int</span> n = cap - <span class="hljs-number">1</span>;
        n |= n &gt;&gt;&gt; <span class="hljs-number">1</span>;
        n |= n &gt;&gt;&gt; <span class="hljs-number">2</span>;
        n |= n &gt;&gt;&gt; <span class="hljs-number">4</span>;
        n |= n &gt;&gt;&gt; <span class="hljs-number">8</span>;
        n |= n &gt;&gt;&gt; <span class="hljs-number">16</span>;
        <span class="hljs-keyword">return</span> (n &lt; <span class="hljs-number">0</span>) ? <span class="hljs-number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="hljs-number">1</span>;
&#125;</code></pre>



<h3 id="5、添加方法"><a href="#5、添加方法" class="headerlink" title="5、添加方法"></a>5、添加方法</h3><h4 id="put-K-V-方法"><a href="#put-K-V-方法" class="headerlink" title="put(K, V)方法"></a>put(K, V)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">put</span><span class="hljs-params">(K key, V value)</span> </span>&#123;
    <span class="hljs-keyword">return</span> putVal(hash(key), key, value, <span class="hljs-keyword">false</span>, <span class="hljs-keyword">true</span>);
&#125;

<span class="hljs-comment">// 因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的</span>
<span class="hljs-comment">// 那么这种处理就可以有效避免类似情况下的哈希碰撞</span>
<span class="hljs-function"><span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> <span class="hljs-title">hash</span><span class="hljs-params">(Object key)</span> </span>&#123;
        <span class="hljs-keyword">int</span> h;
    	<span class="hljs-comment">// 如果key不为null，就让key的高16位和低16位取异或</span>
    	<span class="hljs-comment">// 和Java 7 相比，hash算法确实简单了不少</span>
    	<span class="hljs-comment">// 使用异或尽可能的减少碰撞</span>
        <span class="hljs-keyword">return</span> (key == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="hljs-number">16</span>);
&#125;

<span class="hljs-comment">// 放入元素的操作</span>
<span class="hljs-function"><span class="hljs-keyword">final</span> V <span class="hljs-title">putVal</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, K key, V value, <span class="hljs-keyword">boolean</span> onlyIfAbsent,</span></span>
<span class="hljs-function"><span class="hljs-params">                   <span class="hljs-keyword">boolean</span> evict)</span> </span>&#123;
    	<span class="hljs-comment">// tab相当于哈希表</span>
        Node&lt;K,V&gt;[] tab; 
    	Node&lt;K,V&gt; p; 
    
    	<span class="hljs-comment">// n保存了桶的个数</span>
    	<span class="hljs-comment">// i保存了应放在哪个桶中</span>
    	<span class="hljs-keyword">int</span> n, i;
    
    	<span class="hljs-comment">// 如果还没初始化哈希表，就调用resize方法进行初始化操作</span>
    	<span class="hljs-comment">// resize()方法在后面分析</span>
        <span class="hljs-keyword">if</span> ((tab = table) == <span class="hljs-keyword">null</span> || (n = tab.length) == <span class="hljs-number">0</span>)
            n = (tab = resize()).length;
    
    	
    	<span class="hljs-comment">// 这里的 (n - 1) &amp; hash 相当于 Java 7 中的indexFor()方法，用于确定元素应该放在哪个桶中</span>
    	<span class="hljs-comment">// (n - 1) &amp; hash 有以下两个好处：1、放入的位置不会大于桶的个数（n-1全为1） 2、用到了hash值，确定其应放的对应的位置</span>
        <span class="hljs-keyword">if</span> ((p = tab[i = (n - <span class="hljs-number">1</span>) &amp; hash]) == <span class="hljs-keyword">null</span>)
            <span class="hljs-comment">// 如果桶中没有元素，就将该元素放到对应的桶中</span>
            <span class="hljs-comment">// 把这个元素放到桶中，目前是这个桶里的第一个元素</span>
            tab[i] = newNode(hash, key, value, <span class="hljs-keyword">null</span>);
        <span class="hljs-keyword">else</span> &#123;
            Node&lt;K,V&gt; e; 
            <span class="hljs-comment">// 创建和键类型一致的变量</span>
            K k;
            
            <span class="hljs-comment">// 如果该元素已近存在于哈希表中，就覆盖它</span>
            <span class="hljs-keyword">if</span> (p.hash == hash &amp;&amp;
                ((k = p.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
                e = p;
            <span class="hljs-comment">// 如果采用了红黑树结构，就是用红黑树的插入方法</span>
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (p <span class="hljs-keyword">instanceof</span> TreeNode)
                e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="hljs-keyword">this</span>, tab, hash, key, value);
            <span class="hljs-comment">// 否则，采用链表的扩容方式</span>
            <span class="hljs-keyword">else</span> &#123;
                <span class="hljs-comment">// binCount用于计算桶中元素的个数</span>
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> binCount = <span class="hljs-number">0</span>; ; ++binCount) &#123;
                    <span class="hljs-comment">// 找到插入的位置（链表最后）</span>
                    <span class="hljs-keyword">if</span> ((e = p.next) == <span class="hljs-keyword">null</span>) &#123;
                        <span class="hljs-comment">// 尾插法插入元素</span>
                        p.next = newNode(hash, key, value, <span class="hljs-keyword">null</span>);
                        <span class="hljs-comment">// 如果桶中元素个数大于阈值，就会调用treeifyBin()方法将其结构改为红黑树(但不一定转换成功)</span>
                        <span class="hljs-keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="hljs-number">1</span>) <span class="hljs-comment">// -1 for 1st</span>
                            treeifyBin(tab, hash);
                        <span class="hljs-keyword">break</span>;
                    &#125;
                    <span class="hljs-comment">// 如果遇到了相同的元素，就覆盖它</span>
                    <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;
                        ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
                        <span class="hljs-keyword">break</span>;
                    p = e;
                &#125;
            &#125;
            
            <span class="hljs-keyword">if</span> (e != <span class="hljs-keyword">null</span>) &#123; <span class="hljs-comment">// existing mapping for key</span>
                V oldValue = e.value;
                <span class="hljs-keyword">if</span> (!onlyIfAbsent || oldValue == <span class="hljs-keyword">null</span>)
                    e.value = value;
                afterNodeAccess(e);
                <span class="hljs-keyword">return</span> oldValue;
            &#125;
        &#125;
    
        ++modCount;
    
    	<span class="hljs-comment">// 如果size大于阈值，就进行扩容操作</span>
        <span class="hljs-keyword">if</span> (++size &gt; threshold)
            resize();
    
        afterNodeInsertion(evict);
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
&#125;</code></pre>



<h4 id="resize-扩容方法"><a href="#resize-扩容方法" class="headerlink" title="resize()扩容方法"></a>resize()扩容方法</h4><pre><code class="hljs java"><span class="hljs-keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;
    Node&lt;K,V&gt;[] oldTab = table;
    <span class="hljs-keyword">int</span> oldCap = (oldTab == <span class="hljs-keyword">null</span>) ? <span class="hljs-number">0</span> : oldTab.length;
    <span class="hljs-keyword">int</span> oldThr = threshold;
    <span class="hljs-keyword">int</span> newCap, newThr = <span class="hljs-number">0</span>;
    
    <span class="hljs-comment">// 原容量大于0（已近执行了put操作以后的扩容）</span>
    <span class="hljs-keyword">if</span> (oldCap &gt; <span class="hljs-number">0</span>) &#123;
        <span class="hljs-keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;
            threshold = Integer.MAX_VALUE;
            <span class="hljs-keyword">return</span> oldTab;
        &#125;
        <span class="hljs-comment">// 原容量扩大一倍后小于最大容量，那么newCap就为原容量扩大一倍，同时新阈值为老阈值的一倍</span>
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="hljs-number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;
                 oldCap &gt;= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr &lt;&lt; <span class="hljs-number">1</span>; <span class="hljs-comment">// double threshold</span>
    &#125;
    <span class="hljs-comment">// 调用了含参构造方法的扩容</span>
    <span class="hljs-comment">// 原容量小于等于0，但是阈值大于0，那么新容量就位原来的阈值（阈值在调用构造函数时就会确定，但容量不会）</span>
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (oldThr &gt; <span class="hljs-number">0</span>) <span class="hljs-comment">// initial capacity was placed in threshold</span>
        newCap = oldThr;
    
    <span class="hljs-comment">// 调用了无参构造方法的扩容操作</span>
    <span class="hljs-keyword">else</span> &#123;               
        <span class="hljs-comment">// zero initial threshold signifies using defaults</span>
        <span class="hljs-comment">// 如果连阈值也为0，那就调用的是无参构造方法，就执行初始化操作</span>
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (<span class="hljs-keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    &#125;
    
    <span class="hljs-comment">// 如果新阈值为0，就初始化它</span>
    <span class="hljs-keyword">if</span> (newThr == <span class="hljs-number">0</span>) &#123;
        <span class="hljs-keyword">float</span> ft = (<span class="hljs-keyword">float</span>)newCap * loadFactor;
        newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="hljs-keyword">float</span>)MAXIMUM_CAPACITY ?
                  (<span class="hljs-keyword">int</span>)ft : Integer.MAX_VALUE);
    &#125;
    
    <span class="hljs-comment">// 阈值改为新阈值</span>
    threshold = newThr;
    <span class="hljs-meta">@SuppressWarnings</span>(&#123;<span class="hljs-string">"rawtypes"</span>,<span class="hljs-string">"unchecked"</span>&#125;)
    
    <span class="hljs-comment">// 创建新的表，将旧表中的元素进行重新放入</span>
    Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="hljs-keyword">new</span> Node[newCap];
    table = newTab;
    <span class="hljs-keyword">if</span> (oldTab != <span class="hljs-keyword">null</span>) &#123;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; oldCap; ++j) &#123;
            Node&lt;K,V&gt; e;
            <span class="hljs-keyword">if</span> ((e = oldTab[j]) != <span class="hljs-keyword">null</span>) &#123;
                oldTab[j] = <span class="hljs-keyword">null</span>;
  				<span class="hljs-comment">// 为空就直接放入</span>
                <span class="hljs-keyword">if</span> (e.next == <span class="hljs-keyword">null</span>)
                    newTab[e.hash &amp; (newCap - <span class="hljs-number">1</span>)] = e;
                
                <span class="hljs-comment">// 如果是树节点，就调用红黑树的插入方式</span>
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (e <span class="hljs-keyword">instanceof</span> TreeNode)
                    ((TreeNode&lt;K,V&gt;)e).split(<span class="hljs-keyword">this</span>, newTab, j, oldCap);
                
                <span class="hljs-comment">// 链表的插入操作</span>
                <span class="hljs-keyword">else</span> &#123; <span class="hljs-comment">// preserve order</span>
                    <span class="hljs-comment">// lo 和 hi 分别为两个链表，保存了原来一个桶中元素被拆分后的两个链表</span>
                    Node&lt;K,V&gt; loHead = <span class="hljs-keyword">null</span>, loTail = <span class="hljs-keyword">null</span>;
                    Node&lt;K,V&gt; hiHead = <span class="hljs-keyword">null</span>, hiTail = <span class="hljs-keyword">null</span>;
                    Node&lt;K,V&gt; next;
                    <span class="hljs-keyword">do</span> &#123;
                        next = e.next;
                        <span class="hljs-keyword">if</span> ((e.hash &amp; oldCap) == <span class="hljs-number">0</span>) &#123;
                            <span class="hljs-keyword">if</span> (loTail == <span class="hljs-keyword">null</span>)
                                loHead = e;
                            <span class="hljs-keyword">else</span>
                                loTail.next = e;
                            loTail = e;
                        &#125;
                        <span class="hljs-keyword">else</span> &#123;
                            <span class="hljs-keyword">if</span> (hiTail == <span class="hljs-keyword">null</span>)
                                hiHead = e;
                            <span class="hljs-keyword">else</span>
                                hiTail.next = e;
                            hiTail = e;
                        &#125;
                    &#125; <span class="hljs-keyword">while</span> ((e = next) != <span class="hljs-keyword">null</span>);
                    <span class="hljs-keyword">if</span> (loTail != <span class="hljs-keyword">null</span>) &#123;
                        loTail.next = <span class="hljs-keyword">null</span>;
                        newTab[j] = loHead;
                    &#125;
                    <span class="hljs-keyword">if</span> (hiTail != <span class="hljs-keyword">null</span>) &#123;
                        hiTail.next = <span class="hljs-keyword">null</span>;
                        newTab[j + oldCap] = hiHead;
                    &#125;
                &#125;
            &#125;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> newTab;
&#125;</code></pre>



<p><strong>图解扩容对链表的重构</strong></p>
<ul>
<li>比如哈希表中桶的个数是4个，其中0、4、8、12因为低两位都是0，与 4-1=3(11) 进行按位与后，都被放在了第一个桶中</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913155253.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li><p>然后开始了扩容操作。将元素<strong>哈希值按位与旧容量（不是旧容量-1）</strong>为0的放在lo链表中，不为0的放在hi链表中</p>
<pre><code class="hljs java"><span class="hljs-keyword">do</span> &#123;
    next = e.next;
    <span class="hljs-comment">// 当前元素的hash值和容量进行按位与，决定被分配到哪个链表中</span>
    <span class="hljs-keyword">if</span> ((e.hash &amp; oldCap) == <span class="hljs-number">0</span>) &#123;
        <span class="hljs-keyword">if</span> (loTail == <span class="hljs-keyword">null</span>)
            loHead = e;
        <span class="hljs-keyword">else</span>
            loTail.next = e;
        loTail = e;
    &#125;
    <span class="hljs-keyword">else</span> &#123;
        <span class="hljs-keyword">if</span> (hiTail == <span class="hljs-keyword">null</span>)
            hiHead = e;
        <span class="hljs-keyword">else</span>
            hiTail.next = e;
        hiTail = e;
    &#125;
&#125; <span class="hljs-keyword">while</span> ((e = next) != <span class="hljs-keyword">null</span>);</code></pre>





</li>
</ul>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913155409.png" srcset="/img/loading.gif" alt=""></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913155424.png" srcset="/img/loading.gif" alt=""></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913155454.png" srcset="/img/loading.gif" alt=""></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913155514.png" srcset="/img/loading.gif" alt=""></p>
<ul>
<li>遍历链表，将lo中的放在原来的桶中，hi中的放在增加的桶中</li>
</ul>
<pre><code class="hljs java"><span class="hljs-comment">// 通过头指针直接将链表放入桶中</span>
<span class="hljs-keyword">if</span> (loTail != <span class="hljs-keyword">null</span>) &#123;
    loTail.next = <span class="hljs-keyword">null</span>;
    newTab[j] = loHead;
&#125;
<span class="hljs-keyword">if</span> (hiTail != <span class="hljs-keyword">null</span>) &#123;
    hiTail.next = <span class="hljs-keyword">null</span>;
    newTab[j + oldCap] = hiHead;
&#125;</code></pre>

<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200913155710.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>总结</strong>：</p>
<ul>
<li>先将原桶中的元素的<strong>hash值与旧容量进行按位与</strong>操作<ul>
<li>如果结果为0，就放入lo链表中</li>
<li>如果结果不为0，就放入hi链表中</li>
</ul>
</li>
<li>lo链表中的元素继续放在新的哈希表中原来的位置</li>
<li>hi链表中的元素放在新的哈希表中，扩容后相对于原来的位置上(j+oldCap)<ul>
<li><strong>两个桶之间的间隔数就为增加原来哈希表的容量</strong></li>
</ul>
</li>
</ul>
<p><strong>好处</strong></p>
<ul>
<li>顺序放入，减少了发生死锁的几率</li>
<li>使得元素<strong>相对均匀</strong>地存在于哈希表中</li>
</ul>
<h4 id="putAll-方法"><a href="#putAll-方法" class="headerlink" title="putAll()方法"></a>putAll()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">putAll</span><span class="hljs-params">(Map&lt;? extends K, ? extends V&gt; m)</span> </span>&#123;
    putMapEntries(m, <span class="hljs-keyword">true</span>);
&#125;

<span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">putMapEntries</span><span class="hljs-params">(Map&lt;? extends K, ? extends V&gt; m, <span class="hljs-keyword">boolean</span> evict)</span> </span>&#123;
    	<span class="hljs-comment">// 获得待插入表的大小</span>
        <span class="hljs-keyword">int</span> s = m.size();
    
    	<span class="hljs-comment">// 如果待插入表中有元素</span>
        <span class="hljs-keyword">if</span> (s &gt; <span class="hljs-number">0</span>) &#123;
            <span class="hljs-comment">// 如果当前哈希表为空</span>
            <span class="hljs-keyword">if</span> (table == <span class="hljs-keyword">null</span>) &#123; <span class="hljs-comment">// pre-size</span>
                <span class="hljs-comment">// 容量调整过程，如果超过阈值，就调用tableSizeFor()方法扩容(直接扩容，因为此时哈希表为空)</span>
                <span class="hljs-keyword">float</span> ft = ((<span class="hljs-keyword">float</span>)s / loadFactor) + <span class="hljs-number">1.0F</span>;
                <span class="hljs-keyword">int</span> t = ((ft &lt; (<span class="hljs-keyword">float</span>)MAXIMUM_CAPACITY) ?
                         (<span class="hljs-keyword">int</span>)ft : MAXIMUM_CAPACITY);
                <span class="hljs-keyword">if</span> (t &gt; threshold)
                    threshold = tableSizeFor(t);
            &#125;
            <span class="hljs-comment">// 超过阈值，就调用resize()方法扩容</span>
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (s &gt; threshold)
                resize();
            <span class="hljs-comment">// 把元素依次放入到哈希表中</span>
            <span class="hljs-keyword">for</span> (Map.Entry&lt;? extends K, ? extends V&gt; e : m.entrySet()) &#123;
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, <span class="hljs-keyword">false</span>, evict);
            &#125;
        &#125;
&#125;</code></pre>

<p>最后这里用到了hash()，那就更深入地研究一下吧！</p>
<p><a href="https://www.hollischuang.com/archives/2091" target="_blank" rel="noopener"><strong>全网把Map中的hash()分析的最透彻的文章，别无二家</strong></a></p>
<h3 id="6、移除方法"><a href="#6、移除方法" class="headerlink" title="6、移除方法"></a>6、移除方法</h3><h4 id="remove-方法-1"><a href="#remove-方法-1" class="headerlink" title="remove()方法"></a>remove()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">remove</span><span class="hljs-params">(Object key)</span> </span>&#123;
    Node&lt;K,V&gt; e;
    <span class="hljs-comment">// 调用removeNode()方法，返回其返回的结果</span>
    <span class="hljs-keyword">return</span> (e = removeNode(hash(key), key, <span class="hljs-keyword">null</span>, <span class="hljs-keyword">false</span>, <span class="hljs-keyword">true</span>)) == <span class="hljs-keyword">null</span> ?
        <span class="hljs-keyword">null</span> : e.value;
&#125;

<span class="hljs-function"><span class="hljs-keyword">final</span> Node&lt;K,V&gt; <span class="hljs-title">removeNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, Object key, Object value,</span></span>
<span class="hljs-function"><span class="hljs-params">                               <span class="hljs-keyword">boolean</span> matchValue, <span class="hljs-keyword">boolean</span> movable)</span> </span>&#123;
        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="hljs-keyword">int</span> n, index;
    
    	<span class="hljs-comment">// 桶中有元素, p保存了桶中的首个元素</span>
        <span class="hljs-keyword">if</span> ((tab = table) != <span class="hljs-keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="hljs-number">0</span> &amp;&amp;
            (p = tab[index = (n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) &#123;
            Node&lt;K,V&gt; node = <span class="hljs-keyword">null</span>, e; K k; V v;
            
            <span class="hljs-comment">// 找到对应的元素，保存在node中</span>
            <span class="hljs-keyword">if</span> (p.hash == hash &amp;&amp;
                ((k = p.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
                node = p;
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((e = p.next) != <span class="hljs-keyword">null</span>) &#123;
                <span class="hljs-keyword">if</span> (p <span class="hljs-keyword">instanceof</span> TreeNode)
                    node = ((TreeNode&lt;K,V&gt;)p).getTreeNode(hash, key);
                <span class="hljs-keyword">else</span> &#123;
                    <span class="hljs-comment">// 遍历链表，找到要删除的元素</span>
                    <span class="hljs-keyword">do</span> &#123;
                        <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;
                            ((k = e.key) == key ||
                             (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k)))) &#123;
                            node = e;
                            <span class="hljs-keyword">break</span>;
                        &#125;
                        p = e;
                    &#125; <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);
                &#125;
            &#125;
            
            <span class="hljs-comment">// 该元素不为空</span>
            <span class="hljs-keyword">if</span> (node != <span class="hljs-keyword">null</span> &amp;&amp; (!matchValue || (v = node.value) == value ||
                                 (value != <span class="hljs-keyword">null</span> &amp;&amp; value.equals(v)))) &#123;
                <span class="hljs-comment">// 如果是树节点，就调用红黑树的删除方法</span>
                <span class="hljs-keyword">if</span> (node <span class="hljs-keyword">instanceof</span> TreeNode)
                    ((TreeNode&lt;K,V&gt;)node).removeTreeNode(<span class="hljs-keyword">this</span>, tab, movable);
                <span class="hljs-comment">// 如果是第一个元素，桶的索引就保存其下一个元素</span>
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node == p)
                    tab[index] = node.next;
                
                <span class="hljs-comment">// 否则就不在指向这个元素</span>
                <span class="hljs-keyword">else</span>
                    p.next = node.next;
                
                ++modCount;
                --size;
                afterNodeRemoval(node);
                <span class="hljs-keyword">return</span> node;
            &#125;
        &#125;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
&#125;</code></pre>



<h3 id="7、查找方法"><a href="#7、查找方法" class="headerlink" title="7、查找方法"></a>7、查找方法</h3><h4 id="get-Object-key-方法"><a href="#get-Object-key-方法" class="headerlink" title="get(Object key)方法"></a>get(Object key)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> V <span class="hljs-title">get</span><span class="hljs-params">(Object key)</span> </span>&#123;
    Node&lt;K,V&gt; e;
    <span class="hljs-comment">// 通过key的哈希值和key来进行查找</span>
    <span class="hljs-keyword">return</span> (e = getNode(hash(key), key)) == <span class="hljs-keyword">null</span> ? <span class="hljs-keyword">null</span> : e.value;
&#125;

<span class="hljs-function"><span class="hljs-keyword">final</span> Node&lt;K,V&gt; <span class="hljs-title">getNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> hash, Object key)</span> </span>&#123;
        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="hljs-keyword">int</span> n; K k;
    
    	<span class="hljs-comment">// 哈希表不为空</span>
        <span class="hljs-keyword">if</span> ((tab = table) != <span class="hljs-keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="hljs-number">0</span> &amp;&amp;
            (first = tab[(n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) &#123;
            
            <span class="hljs-comment">// 如果第一个元素就是要查找的元素，就返回</span>
            <span class="hljs-keyword">if</span> (first.hash == hash &amp;&amp; <span class="hljs-comment">// always check first node</span>
                ((k = first.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
                <span class="hljs-keyword">return</span> first;
            
            <span class="hljs-comment">// 如果第一个元素不是，就继续往后找。找到就返回，没至找到就返回null</span>
            <span class="hljs-keyword">if</span> ((e = first.next) != <span class="hljs-keyword">null</span>) &#123;
                <span class="hljs-keyword">if</span> (first <span class="hljs-keyword">instanceof</span> TreeNode)
                    <span class="hljs-keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
                <span class="hljs-keyword">do</span> &#123;
                    <span class="hljs-keyword">if</span> (e.hash == hash &amp;&amp;
                        ((k = e.key) == key || (key != <span class="hljs-keyword">null</span> &amp;&amp; key.equals(k))))
                        <span class="hljs-keyword">return</span> e;
                &#125; <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);
            &#125;
        &#125;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
&#125;</code></pre>



<h3 id="8、树化方法"><a href="#8、树化方法" class="headerlink" title="8、树化方法"></a>8、树化方法</h3><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">final</span> <span class="hljs-keyword">void</span> <span class="hljs-title">treeifyBin</span><span class="hljs-params">(Node&lt;K,V&gt;[] tab, <span class="hljs-keyword">int</span> hash)</span> </span>&#123;
    <span class="hljs-keyword">int</span> n, index; Node&lt;K,V&gt; e;
    
    <span class="hljs-comment">// 如果当前哈希表中桶的数目，小于最小树化容量，就调用resize()方法进行扩容</span>
    <span class="hljs-keyword">if</span> (tab == <span class="hljs-keyword">null</span> || (n = tab.length) &lt; MIN_TREEIFY_CAPACITY)
        resize();
    
    <span class="hljs-comment">// 当桶中元素个数大于8，且桶的个数大于64时，进行树化</span>
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((e = tab[index = (n - <span class="hljs-number">1</span>) &amp; hash]) != <span class="hljs-keyword">null</span>) &#123;
        TreeNode&lt;K,V&gt; hd = <span class="hljs-keyword">null</span>, tl = <span class="hljs-keyword">null</span>;
        <span class="hljs-keyword">do</span> &#123;
            TreeNode&lt;K,V&gt; p = replacementTreeNode(e, <span class="hljs-keyword">null</span>);
            <span class="hljs-keyword">if</span> (tl == <span class="hljs-keyword">null</span>)
                hd = p;
            <span class="hljs-keyword">else</span> &#123;
                p.prev = tl;
                tl.next = p;
            &#125;
            tl = p;
        &#125; <span class="hljs-keyword">while</span> ((e = e.next) != <span class="hljs-keyword">null</span>);
        <span class="hljs-keyword">if</span> ((tab[index] = hd) != <span class="hljs-keyword">null</span>)
            hd.treeify(tab);
    &#125;
&#125;</code></pre>

<p><strong>链表变为红黑树的条件</strong>：元素个数大于8同时桶的个数大于64</p>
<ul>
<li>当某个桶中的<strong>元素个数大于8</strong>时，会调用treeifyBin()方法，但并不一定就会变为红黑树</li>
<li>当哈希表中<strong>桶的个数大于64</strong>时，才会真正进行让其转化为红黑树</li>
</ul>
<p><strong>为什么</strong>桶中元素多于了8个，桶的个数小于64，<strong>调用resize()方法就可以进行调整</strong>？</p>
<ul>
<li>因为调用resize()方法进行扩容时，会让同一个桶中的<strong>元素进行桶的重新分配</strong>。一部分会被放新哈希表中在原来的位置上，一部分会被放在扩容后的位置上</li>
</ul>
<p>详见上面<a href="https://nyimac.gitee.io/2020/09/10/%E9%9B%86%E5%90%88%E6%BA%90%E7%A0%81/#resize-%E6%89%A9%E5%AE%B9%E6%96%B9%E6%B3%95"><strong>resize()方法的分析和图解</strong></a></p>
<h1 id="PriorityQueue"><a href="#PriorityQueue" class="headerlink" title="PriorityQueue"></a>PriorityQueue</h1><h2 id="一、优先队列简介"><a href="#一、优先队列简介" class="headerlink" title="一、优先队列简介"></a>一、优先队列简介</h2><h3 id="1、概念"><a href="#1、概念" class="headerlink" title="1、概念"></a>1、概念</h3><p>平时我们了解到的队列，是一种满足<strong>先进先出</strong>的线性数据结构。优先队列与其有相似之处，但是也有所不同。</p>
<p>当我们向优先队列中插入元素的时候，<strong>优先队列会根据一定的条件将该元素插入到合适的位置</strong></p>
<h3 id="2、演示"><a href="#2、演示" class="headerlink" title="2、演示"></a>2、演示</h3><p>创建一个一般队列Queue和优先队列PriorityQueue，分别向队列中以 2、1、3的顺序放入元素，观察他们的遍历结果</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo3</span> </span>&#123;
   <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
      Queue&lt;Integer&gt; normalQueue = <span class="hljs-keyword">new</span> LinkedList&lt;&gt;();
      normalQueue.add(<span class="hljs-number">2</span>);
      normalQueue.add(<span class="hljs-number">1</span>);
      normalQueue.add(<span class="hljs-number">3</span>);
      System.out.println(<span class="hljs-string">"一般队列元素顺序"</span>);
      <span class="hljs-keyword">for</span> (Integer num : normalQueue) &#123;
         System.out.print(num + <span class="hljs-string">" "</span>);
      &#125;
      System.out.println();

      PriorityQueue&lt;Integer&gt; priorityQueue = <span class="hljs-keyword">new</span> PriorityQueue&lt;&gt;();
      priorityQueue.add(<span class="hljs-number">2</span>);
      priorityQueue.add(<span class="hljs-number">1</span>);
      priorityQueue.add(<span class="hljs-number">3</span>);
      System.out.println(<span class="hljs-string">"优先队列元素顺序"</span>);
      <span class="hljs-keyword">for</span> (Integer num : priorityQueue) &#123;
         System.out.print(num + <span class="hljs-string">" "</span>);
      &#125;
   &#125;
&#125;</code></pre>

<p><strong>运行结果</strong></p>
<pre><code class="hljs angelscript">一般队列元素顺序
<span class="hljs-number">2</span> <span class="hljs-number">1</span> <span class="hljs-number">3</span> 
优先队列元素顺序
<span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span></code></pre>



<h3 id="3、Comparator接口"><a href="#3、Comparator接口" class="headerlink" title="3、Comparator接口"></a>3、Comparator接口</h3><p>当我们想根据对象中的某些特定属性，来对对象进行排序的话，需要实现Comparator中的compare方法</p>
<pre><code class="hljs java"><span class="hljs-meta">@Override</span>
<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compare</span><span class="hljs-params">(Object o1, Object o2)</span> </span>&#123;
    <span class="hljs-comment">// o1为待插入元素，o2为被比较元素</span>
    <span class="hljs-keyword">return</span> o1.val - o2.val;
&#125;</code></pre>



<h3 id="4、-Comparable接口"><a href="#4、-Comparable接口" class="headerlink" title="4、 Comparable接口"></a>4、 Comparable接口</h3><p>基本类型的包装类、集合类与接口几乎都实现了这个接口</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200930152042.png" srcset="/img/loading.gif" alt=""></p>
<p>该接口中的compareTo(T o)一般<strong>用于比较包装类型的大小</strong></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compareTo</span><span class="hljs-params">(T o)</span></span>;</code></pre>



<p>如Integer类中的该方法</p>
<p>如果该值大于被比较的值，则返回1</p>
<p>相等则返回0，小于则返回-1</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compareTo</span><span class="hljs-params">(Integer anotherInteger)</span> </span>&#123;
    <span class="hljs-keyword">return</span> compare(<span class="hljs-keyword">this</span>.value, anotherInteger.value);
&#125;</code></pre>

<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compare</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x, <span class="hljs-keyword">int</span> y)</span> </span>&#123;
    <span class="hljs-keyword">return</span> (x &lt; y) ? -<span class="hljs-number">1</span> : ((x == y) ? <span class="hljs-number">0</span> : <span class="hljs-number">1</span>);
&#125;</code></pre>





<h3 id="5、按对象中的特定值进行插入"><a href="#5、按对象中的特定值进行插入" class="headerlink" title="5、按对象中的特定值进行插入"></a>5、按对象中的特定值进行插入</h3><p>如果我们想将<strong>对象</strong>放入PriorityQueue中，并<strong>按照指定的方式进行排序</strong>，可以这样做</p>
<p>创建优先队列是，传入Comparator对象，并重写其compare方法，则会按照我们设定的规定进行比较</p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Demo4</span> </span>&#123;
   <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
      <span class="hljs-comment">// 创建优先队列，传入Comparator对象，并重写其compare方法</span>
      PriorityQueue&lt;Student&gt; priorityQueue = <span class="hljs-keyword">new</span> PriorityQueue&lt;&gt;(<span class="hljs-keyword">new</span> Comparator&lt;Student&gt;() &#123;
         <span class="hljs-meta">@Override</span>
         <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compare</span><span class="hljs-params">(Student o1, Student o2)</span> </span>&#123;
            <span class="hljs-comment">// 其中o1为要插入的值，o2为比较的目标值</span>
            <span class="hljs-keyword">return</span> o1.getAge() - o2.getAge();
         &#125;
      &#125;);

      Student st1 = <span class="hljs-keyword">new</span> Student(<span class="hljs-string">"A"</span>, <span class="hljs-number">3</span>);
      Student st2 = <span class="hljs-keyword">new</span> Student(<span class="hljs-string">"B"</span>, <span class="hljs-number">1</span>);
      Student st3 = <span class="hljs-keyword">new</span> Student(<span class="hljs-string">"C"</span>, <span class="hljs-number">2</span>);

      priorityQueue.add(st1);
      priorityQueue.add(st2);
      priorityQueue.add(st3);

      <span class="hljs-keyword">while</span> (!priorityQueue.isEmpty()) &#123;
         System.out.println(priorityQueue.remove());
      &#125;
   &#125;
&#125;

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Student</span> </span>&#123;
   <span class="hljs-keyword">private</span> String name;
   <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> age;

   <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Student</span><span class="hljs-params">(String name, <span class="hljs-keyword">int</span> age)</span> </span>&#123;
      <span class="hljs-keyword">this</span>.name = name;
      <span class="hljs-keyword">this</span>.age = age;
   &#125;

   <span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">getName</span><span class="hljs-params">()</span> </span>&#123;
      <span class="hljs-keyword">return</span> name;
   &#125;

   <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setName</span><span class="hljs-params">(String name)</span> </span>&#123;
      <span class="hljs-keyword">this</span>.name = name;
   &#125;

   <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getAge</span><span class="hljs-params">()</span> </span>&#123;
      <span class="hljs-keyword">return</span> age;
   &#125;

   <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setAge</span><span class="hljs-params">(<span class="hljs-keyword">int</span> age)</span> </span>&#123;
      <span class="hljs-keyword">this</span>.age = age;
   &#125;

   <span class="hljs-meta">@Override</span>
   <span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">toString</span><span class="hljs-params">()</span> </span>&#123;
      <span class="hljs-keyword">return</span> <span class="hljs-string">"Student&#123;"</span> +
            <span class="hljs-string">"name='"</span> + name + <span class="hljs-string">'\''</span> +
            <span class="hljs-string">", age="</span> + age +
            <span class="hljs-string">'&#125;'</span>;
   &#125;
&#125;</code></pre>



<h2 id="二、大顶堆和小顶堆"><a href="#二、大顶堆和小顶堆" class="headerlink" title="二、大顶堆和小顶堆"></a>二、大顶堆和小顶堆</h2><h3 id="1、基本介绍"><a href="#1、基本介绍" class="headerlink" title="1、基本介绍"></a>1、基本介绍</h3><p>大顶堆和小顶堆都是完全二叉树，并且具有以下性质</p>
<p><strong>大顶堆</strong></p>
<ul>
<li>根节点的值都大于其所有孩子的值</li>
</ul>
<p><strong>小顶堆</strong></p>
<ul>
<li>根节点的值都小于其所有孩子的值</li>
</ul>
<p>因为大顶堆小顶堆都是完全二叉树，所以大顶堆和小顶堆都<strong>可以用数组加以表示</strong></p>
<p>如果一个数组，根节点的下标为index</p>
<ul>
<li>那么它左孩子的下标为2*index+1，</li>
<li>右孩子的值为2*(index+1)</li>
</ul>
<p><strong>以小顶堆为例</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200930140529.png" srcset="/img/loading.gif" alt=""></p>
<h3 id="2、如何构造"><a href="#2、如何构造" class="headerlink" title="2、如何构造"></a>2、如何构造</h3><p>若我们要构建小顶堆，当叶子节点的值小于其父节点的值时，将其于其父节点的值进行交换，知道换在了合适的位置上。我们称这个过程为<strong>上浮</strong></p>
<p>详见：<a href="https://nyimac.gitee.io/2020/06/17/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/#11%E3%80%81%E5%A0%86%E6%8E%92%E5%BA%8F"><strong>Java数据结构与算法——堆排序</strong></a></p>
<h2 id="三、属性和存储结构"><a href="#三、属性和存储结构" class="headerlink" title="三、属性和存储结构"></a>三、属性和存储结构</h2><pre><code class="hljs java"><span class="hljs-comment">// 默认容量大小</span>
<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="hljs-number">11</span>;

<span class="hljs-comment">// Object数组，用于存放我们的元素,在操作过程中体现为堆</span>
<span class="hljs-keyword">transient</span> Object[] queue; <span class="hljs-comment">// non-private to simplify nested class access</span>

<span class="hljs-comment">// 数组中元素的个数</span>
<span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> size = <span class="hljs-number">0</span>;

<span class="hljs-comment">// 比较器，其中的compare方法可用于比较插入元素的值</span>
<span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> Comparator&lt;? <span class="hljs-keyword">super</span> E&gt; comparator;

<span class="hljs-comment">// 操作次数计数器</span>
<span class="hljs-keyword">transient</span> <span class="hljs-keyword">int</span> modCount = <span class="hljs-number">0</span></code></pre>





<h2 id="四、构造方法"><a href="#四、构造方法" class="headerlink" title="四、构造方法"></a>四、构造方法</h2><h3 id="1、默认构造方法"><a href="#1、默认构造方法" class="headerlink" title="1、默认构造方法"></a>1、默认构造方法</h3><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">()</span> </span>&#123;
    <span class="hljs-keyword">this</span>(DEFAULT_INITIAL_CAPACITY, <span class="hljs-keyword">null</span>);
&#125;</code></pre>





<h3 id="2、带初始容量构造方法"><a href="#2、带初始容量构造方法" class="headerlink" title="2、带初始容量构造方法"></a>2、带初始容量构造方法</h3><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity)</span> </span>&#123;
    <span class="hljs-keyword">this</span>(initialCapacity, <span class="hljs-keyword">null</span>);
&#125;</code></pre>



<h3 id="3、带比较器的构造方法"><a href="#3、带比较器的构造方法" class="headerlink" title="3、带比较器的构造方法"></a>3、带比较器的构造方法</h3><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">(Comparator&lt;? <span class="hljs-keyword">super</span> E&gt; comparator)</span> </span>&#123;
    <span class="hljs-keyword">this</span>(DEFAULT_INITIAL_CAPACITY, comparator);
&#125;</code></pre>



<h3 id="4、带容量和比较器的构造方法"><a href="#4、带容量和比较器的构造方法" class="headerlink" title="4、带容量和比较器的构造方法"></a>4、带容量和比较器的构造方法</h3><p>从上面的三个构造函数可以看出，<strong>最终调用的都是这个构造函数</strong>。如果没有指定容量，就是用默认容量，如果没有指定比较器，就是用默认比较器</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">PriorityQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> initialCapacity,</span></span>
<span class="hljs-function"><span class="hljs-params">                     Comparator&lt;? <span class="hljs-keyword">super</span> E&gt; comparator)</span> </span>&#123;
    <span class="hljs-comment">// Note: This restriction of at least one is not actually needed,</span>
    <span class="hljs-comment">// but continues for 1.5 compatibility</span>
    <span class="hljs-keyword">if</span> (initialCapacity &lt; <span class="hljs-number">1</span>)
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException();
    <span class="hljs-comment">// 初始化数组</span>
    <span class="hljs-keyword">this</span>.queue = <span class="hljs-keyword">new</span> Object[initialCapacity];
    <span class="hljs-comment">// 给比较器赋值</span>
    <span class="hljs-keyword">this</span>.comparator = comparator;
&#125;</code></pre>



<h2 id="五、添加方法"><a href="#五、添加方法" class="headerlink" title="五、添加方法"></a>五、添加方法</h2><h3 id="1、add-E-e-方法"><a href="#1、add-E-e-方法" class="headerlink" title="1、add(E e)方法"></a>1、add(E e)方法</h3><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">add</span><span class="hljs-params">(E e)</span> </span>&#123;
    <span class="hljs-keyword">return</span> offer(e);
&#125;</code></pre>



<h3 id="2、offer-E-e-方法"><a href="#2、offer-E-e-方法" class="headerlink" title="2、offer(E e)方法"></a>2、offer(E e)方法</h3><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">offer</span><span class="hljs-params">(E e)</span> </span>&#123;
    <span class="hljs-keyword">if</span> (e == <span class="hljs-keyword">null</span>)
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NullPointerException();
    modCount++;
    <span class="hljs-comment">// 保存当前元素的个数</span>
    <span class="hljs-keyword">int</span> i = size;
    <span class="hljs-comment">// 如果元素大于了Object数组的长度，就进行扩容</span>
    <span class="hljs-keyword">if</span> (i &gt;= queue.length)
        grow(i + <span class="hljs-number">1</span>);
    <span class="hljs-comment">// 否则元素个数+1</span>
    size = i + <span class="hljs-number">1</span>;
    <span class="hljs-comment">// 如果数组中还没有元素，就直接放入</span>
    <span class="hljs-keyword">if</span> (i == <span class="hljs-number">0</span>)
        queue[<span class="hljs-number">0</span>] = e;
    <span class="hljs-comment">// 否则，进行调整操作</span>
    <span class="hljs-comment">// 其中i为队列最后一个元素的下一个位置，e为待插入元素</span>
    <span class="hljs-keyword">else</span>
        siftUp(i, e);
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
&#125;</code></pre>



<h4 id="grow-int-minCapacity-方法"><a href="#grow-int-minCapacity-方法" class="headerlink" title="grow(int minCapacity)方法"></a>grow(int minCapacity)方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">grow</span><span class="hljs-params">(<span class="hljs-keyword">int</span> minCapacity)</span> </span>&#123;
    <span class="hljs-keyword">int</span> oldCapacity = queue.length;
    <span class="hljs-comment">// Double size if small; else grow by 50%</span>
    <span class="hljs-comment">// 如果队列容量小于64，就按照两倍扩容，否则就扩容50%</span>
    <span class="hljs-comment">// 如 20 -&gt; 42    100 -&gt; 150</span>
    <span class="hljs-keyword">int</span> newCapacity = oldCapacity + ((oldCapacity &lt; <span class="hljs-number">64</span>) ?
                                     (oldCapacity + <span class="hljs-number">2</span>) :
                                     (oldCapacity &gt;&gt; <span class="hljs-number">1</span>));
    <span class="hljs-comment">// overflow-conscious code</span>
    <span class="hljs-keyword">if</span> (newCapacity - MAX_ARRAY_SIZE &gt; <span class="hljs-number">0</span>)
        newCapacity = hugeCapacity(minCapacity);
    
    <span class="hljs-comment">// 扩容后的复制操作</span>
    queue = Arrays.copyOf(queue, newCapacity);
&#125;</code></pre>



<h4 id="siftUp-int-k-E-x-函数"><a href="#siftUp-int-k-E-x-函数" class="headerlink" title="siftUp(int k, E x)函数"></a>siftUp(int k, E x)函数</h4><p>其中k为队列最后一个元素的<strong>下一个位置</strong>，x为<strong>待插入元素</strong></p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftUp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;
    <span class="hljs-comment">// 如果指定了比较器，就使用指定比较器的比较方法</span>
    <span class="hljs-keyword">if</span> (comparator != <span class="hljs-keyword">null</span>)
        siftUpUsingComparator(k, x);
    <span class="hljs-comment">// 否则就使用默认的比较方法</span>
    <span class="hljs-keyword">else</span>
        siftUpComparable(k, x);
&#125;</code></pre>



<h4 id="指定了比较器的比较方法siftUpUsingComparator-int-k-E-x"><a href="#指定了比较器的比较方法siftUpUsingComparator-int-k-E-x" class="headerlink" title="指定了比较器的比较方法siftUpUsingComparator(int k, E x)"></a>指定了比较器的比较方法siftUpUsingComparator(int k, E x)</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftUpUsingComparator</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;
    <span class="hljs-comment">// 如果要放入的位置不是根节点，就继续</span>
    <span class="hljs-keyword">while</span> (k &gt; <span class="hljs-number">0</span>) &#123;
        <span class="hljs-comment">// 得到该元素的父节点</span>
        <span class="hljs-keyword">int</span> parent = (k - <span class="hljs-number">1</span>) &gt;&gt;&gt; <span class="hljs-number">1</span>;
        
        <span class="hljs-comment">// 保存其父节点</span>
        Object e = queue[parent];
        
        <span class="hljs-comment">// 如果父节点的值小于插入节点的值，就停止循环</span>
        <span class="hljs-keyword">if</span> (comparator.compare(x, (E) e) &gt;= <span class="hljs-number">0</span>)
            <span class="hljs-keyword">break</span>;
        
        <span class="hljs-comment">// 否则父节点下沉(插入元素上浮)</span>
        queue[k] = e;
        
        <span class="hljs-comment">// k保存其父节点的位置</span>
        k = parent;
    &#125;
    <span class="hljs-comment">// 将待插入元素放到对应的位置</span>
    queue[k] = x;
&#125;</code></pre>



<p><strong>图解</strong></p>
<p>如果小顶堆中要插入元素3</p>
<p><strong>此时k = 4</strong>，我们通过 <strong>parent = (k-1)/2</strong>，可以得到父节点的下标为1，也是就元素4所在的位置</p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200930144311.png" srcset="/img/loading.gif" alt=""></p>
<p>3和4通过compare函数进行比较，结果小于0，待插入元素需要上浮，父节点元素需要下沉<strong>queue[k] = e</strong></p>
<p>然后令 <strong>k = parrent</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200930144459.png" srcset="/img/loading.gif" alt=""></p>
<p>再次计算父节点的下标 <strong>parent = (k-1)/2 = 0</strong>，也就是元素1</p>
<p>1与3比较，3&gt;1，结束循环</p>
<pre><code class="hljs java"><span class="hljs-keyword">if</span> (comparator.compare(x, (E) e) &gt;= <span class="hljs-number">0</span>)
      <span class="hljs-keyword">break</span>;</code></pre>

<p>将待插入元素放到对应位置<strong>queue[k] = x</strong></p>
<p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200930144649.png" srcset="/img/loading.gif" alt=""></p>
<p><strong>总结</strong>：可以看到，待插入元素一直在与其父节点进行比较，如果待插入元素的值小于父节点，则待父节点下沉，待插入元素上浮</p>
<h4 id="默认比较方法siftUpComparable-int-k-E-x"><a href="#默认比较方法siftUpComparable-int-k-E-x" class="headerlink" title="默认比较方法siftUpComparable(int k, E x)"></a>默认比较方法siftUpComparable(int k, E x)</h4><p>和指定了比较器的比较方法类似，只不过是通过Comparable来实现的</p>
<h2 id="六、移除元素"><a href="#六、移除元素" class="headerlink" title="六、移除元素"></a>六、移除元素</h2><h3 id="1、remove-函数"><a href="#1、remove-函数" class="headerlink" title="1、remove()函数"></a>1、remove()函数</h3><p>调用父类AbstractQueue的remove()函数</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">remove</span><span class="hljs-params">()</span> </span>&#123;
    <span class="hljs-comment">// 调用改类的poll函数</span>
    E x = poll();
    <span class="hljs-keyword">if</span> (x != <span class="hljs-keyword">null</span>)
        <span class="hljs-keyword">return</span> x;
    <span class="hljs-keyword">else</span>
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NoSuchElementException();
&#125;</code></pre>



<h4 id="poll-函数"><a href="#poll-函数" class="headerlink" title="poll()函数"></a>poll()函数</h4><p>移除队首元素</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> E <span class="hljs-title">poll</span><span class="hljs-params">()</span> </span>&#123;
    <span class="hljs-keyword">if</span> (size == <span class="hljs-number">0</span>)
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
    <span class="hljs-comment">// s为新的元素个数</span>
    <span class="hljs-keyword">int</span> s = --size;
    modCount++;
    <span class="hljs-comment">// 队首元素</span>
    E result = (E) queue[<span class="hljs-number">0</span>];
    
    <span class="hljs-comment">// 保存最后一个元素</span>
    E x = (E) queue[s];
    queue[s] = <span class="hljs-keyword">null</span>;
    
    <span class="hljs-comment">// 如果队列中还有元素</span>
    <span class="hljs-keyword">if</span> (s != <span class="hljs-number">0</span>)
        <span class="hljs-comment">// 下沉</span>
        siftDown(<span class="hljs-number">0</span>, x);
    <span class="hljs-keyword">return</span> result;
&#125;</code></pre>



<h4 id="siftDown-int-k-E-x-函数"><a href="#siftDown-int-k-E-x-函数" class="headerlink" title="siftDown(int k, E x)函数"></a>siftDown(int k, E x)函数</h4><p>k为移除元素的位置，x为队尾元素</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftDown</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;
    <span class="hljs-keyword">if</span> (comparator != <span class="hljs-keyword">null</span>)
        siftDownUsingComparator(k, x);
    <span class="hljs-keyword">else</span>
        siftDownComparable(k, x);
&#125;</code></pre>



<h4 id="指定了比较器的siftDownUsingComparator-int-k-E-x-函数"><a href="#指定了比较器的siftDownUsingComparator-int-k-E-x-函数" class="headerlink" title="指定了比较器的siftDownUsingComparator(int k, E x)函数"></a>指定了比较器的siftDownUsingComparator(int k, E x)函数</h4><p>调整小顶堆，让其保持其特性</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">siftDownUsingComparator</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k, E x)</span> </span>&#123;
    <span class="hljs-keyword">int</span> half = size &gt;&gt;&gt; <span class="hljs-number">1</span>;
    <span class="hljs-keyword">while</span> (k &lt; half) &#123;
        <span class="hljs-comment">// 删除节点的左孩子的下标</span>
        <span class="hljs-keyword">int</span> child = (k &lt;&lt; <span class="hljs-number">1</span>) + <span class="hljs-number">1</span>;
        
        <span class="hljs-comment">// c保存了左孩子的值</span>
        Object c = queue[child];
        
        <span class="hljs-comment">// 删除节点的右孩子的下标</span>
        <span class="hljs-keyword">int</span> right = child + <span class="hljs-number">1</span>;
        
        <span class="hljs-comment">// 如果右孩子小标小于size 并且 右孩子的值小于左孩子</span>
        <span class="hljs-keyword">if</span> (right &lt; size &amp;&amp;
            comparator.compare((E) c, (E) queue[right]) &gt; <span class="hljs-number">0</span>)
            
            <span class="hljs-comment">// child保存右孩子小标，c保存右孩子</span>
            c = queue[child = right];
        
        <span class="hljs-comment">// 如果队尾元素小于c的值，就停止</span>
        <span class="hljs-keyword">if</span> (comparator.compare(x, (E) c) &lt;= <span class="hljs-number">0</span>)
            <span class="hljs-keyword">break</span>;
        
        <span class="hljs-comment">// 下沉</span>
        queue[k] = c;
        k = child;
    &#125;
    <span class="hljs-comment">// 赋值</span>
    queue[k] = x;
&#125;</code></pre>



<h4 id="siftDownComparable-int-k-E-x"><a href="#siftDownComparable-int-k-E-x" class="headerlink" title="siftDownComparable(int k, E x)"></a>siftDownComparable(int k, E x)</h4><p>和指定了比较器的比较方法类似，只不过是通过Comparable来实现的</p>
<h3 id="2、remove-Object-o-方法"><a href="#2、remove-Object-o-方法" class="headerlink" title="2、remove(Object o)方法"></a>2、remove(Object o)方法</h3><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">remove</span><span class="hljs-params">(Object o)</span> </span>&#123;
    <span class="hljs-comment">// 找到移除元素的下标</span>
    <span class="hljs-keyword">int</span> i = indexOf(o);
    <span class="hljs-keyword">if</span> (i == -<span class="hljs-number">1</span>)
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
    <span class="hljs-keyword">else</span> &#123;
        <span class="hljs-comment">// 移除该元素</span>
        removeAt(i);
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
    &#125;
&#125;</code></pre>



<h4 id="indexOf-方法"><a href="#indexOf-方法" class="headerlink" title="indexOf()方法"></a>indexOf()方法</h4><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">indexOf</span><span class="hljs-params">(Object o)</span> </span>&#123;
    <span class="hljs-keyword">if</span> (o != <span class="hljs-keyword">null</span>) &#123;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; size; i++)
            <span class="hljs-comment">// 找到该对象并返回</span>
            <span class="hljs-keyword">if</span> (o.equals(queue[i]))
                <span class="hljs-keyword">return</span> i;
    &#125;
    <span class="hljs-keyword">return</span> -<span class="hljs-number">1</span>;
&#125;</code></pre>



<h4 id="removeAt-int-i-方法"><a href="#removeAt-int-i-方法" class="headerlink" title="removeAt(int i)方法"></a>removeAt(int i)方法</h4><p>移除指定元素，保证移除后仍为小顶堆</p>
<pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">private</span> E <span class="hljs-title">removeAt</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i)</span> </span>&#123;
    <span class="hljs-comment">// assert i &gt;= 0 &amp;&amp; i &lt; size;</span>
    modCount++;
    <span class="hljs-keyword">int</span> s = --size;
    <span class="hljs-keyword">if</span> (s == i) <span class="hljs-comment">// removed last element</span>
        queue[i] = <span class="hljs-keyword">null</span>;
    <span class="hljs-keyword">else</span> &#123;
        E moved = (E) queue[s];
        queue[s] = <span class="hljs-keyword">null</span>;
        siftDown(i, moved);
        <span class="hljs-keyword">if</span> (queue[i] == moved) &#123;
            siftUp(i, moved);
            <span class="hljs-keyword">if</span> (queue[i] != moved)
                <span class="hljs-keyword">return</span> moved;
        &#125;
    &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
&#125;</code></pre>



<h2 id="六、优先队列的应用"><a href="#六、优先队列的应用" class="headerlink" title="六、优先队列的应用"></a>六、优先队列的应用</h2><h4 id="LeetCode–347-前-K-个高频元素"><a href="#LeetCode–347-前-K-个高频元素" class="headerlink" title="LeetCode–347. 前 K 个高频元素"></a><a href="https://leetcode-cn.com/problems/top-k-frequent-elements/" target="_blank" rel="noopener">LeetCode–347. 前 K 个高频元素</a></h4><p><img src="https://nyimapicture.oss-cn-beijing.aliyuncs.com/img/20200930152616.png" srcset="/img/loading.gif" alt=""></p>
<pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span>[] topKFrequent(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> k) &#123;
   <span class="hljs-comment">// 哈希表，用于存放数字出现的次数</span>
   <span class="hljs-comment">// key：数字 value：出现次数</span>
   <span class="hljs-keyword">int</span> length = nums.length;
   HashMap&lt;Integer, Integer&gt; map = <span class="hljs-keyword">new</span> HashMap&lt;&gt;(length);

   <span class="hljs-comment">// 遍历数组</span>
   <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; length; i++) &#123;
      <span class="hljs-keyword">if</span> (!map.containsKey(nums[i])) &#123;
         <span class="hljs-comment">// 如果该数字是第一次出现，直接放入哈希表中</span>
         map.put(nums[i], <span class="hljs-number">1</span>);
      &#125; <span class="hljs-keyword">else</span> &#123;
         <span class="hljs-comment">// 否则，将其出现次数+1</span>
         map.put(nums[i], map.get(nums[i]) + <span class="hljs-number">1</span>);
      &#125;
   &#125;

   <span class="hljs-comment">// 创建优先队列，小顶堆</span>
   PriorityQueue&lt;Integer&gt; priorityQueue = <span class="hljs-keyword">new</span> PriorityQueue&lt;&gt;(k, <span class="hljs-keyword">new</span> Comparator&lt;Integer&gt;() &#123;
      <span class="hljs-meta">@Override</span>
      <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compare</span><span class="hljs-params">(Integer o1, Integer o2)</span> </span>&#123;
         <span class="hljs-comment">// 插入元素与队尾元素的插值</span>
         <span class="hljs-keyword">return</span> map.get(o1) - map.get(o2);
      &#125;
   &#125;);

   <span class="hljs-keyword">for</span> (Integer key : map.keySet()) &#123;
      <span class="hljs-keyword">if</span> (priorityQueue.size() &lt; k) &#123;
         priorityQueue.add(key);
      &#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (map.get(key) &gt; map.get(priorityQueue.peek())) &#123;
         <span class="hljs-comment">// 次数最少的元素在队首</span>
         priorityQueue.remove();
         <span class="hljs-comment">// 放入该数字</span>
         priorityQueue.add(key);
      &#125;
   &#125;

   <span class="hljs-keyword">int</span> size = priorityQueue.size();
   <span class="hljs-keyword">int</span>[] result = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[size];
   <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = size-<span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span> ; i--) &#123;
      result[i] = priorityQueue.remove();
   &#125;
   <span class="hljs-keyword">return</span> result;
&#125;</code></pre>



            </article>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/2020/11/03/%E4%BB%A3%E7%90%86%E6%A8%A1%E5%BC%8F/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">代理模式</span>
                        <span class="visible-mobile">Previous</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/2020/10/13/%E6%B3%A8%E8%A7%A3%E4%B8%8E%E5%8F%8D%E5%B0%84/">
                        <span class="hidden-mobile">注解与反射</span>
                        <span class="visible-mobile">Next</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

            
              <!-- Comments -->
              <div class="comments" id="comments">
                
                
  <div class="disqus" style="width:100%">
    <div id="disqus_thread"></div>
    <script type="text/javascript">
      function loadDisqus() {
        var disqus_config = function () {
          this.page.url = 'http://nyimac.gitee.io/2020/10/26/集合源码/';
          this.page.identifier = '/2020/10/26/集合源码/';
        };
        (function () {
          var d = document,
            s = d.createElement('script');
          s.src = '//' + '' + '.disqus.com/embed.js';
          s.setAttribute('data-timestamp', new Date());
          (d.head || d.body).appendChild(s);
        })();
      }
      createObserver(loadDisqus, 'disqus_thread');
    </script>
    <noscript>Please enable JavaScript to view the
      <a href="https://disqus.com/?ref_noscript" target="_blank" rel="nofollow noopener noopener">comments powered by Disqus.</a>
    </noscript>
  </div>


              </div>
            
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;TOC</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: 'article.markdown-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "集合源码&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>

















  
    <!-- Baidu Analytics -->
    <script defer>
      var _hmt = _hmt || [];
      (function () {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?ba41ec605b9b7320e120275462e4035b";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>
  

  

  

  

  

  





</body>
</html>
